梦梦得到了一串正整数序列： A = (A1, A2, ..., AN)。

梦梦将重复以下操作，直到序列 A 的长度变为 1 为止： 设操作前 A 的长度为 k。选择整数 i 和 j，使得

max(A1, A2, ..., AN)=Ai，min(A1, A2, ..., AN)=Aj ， 且i≠j 。然后(Ai mod Aj)，用  替换 Ai。如果此时 Ai 变为 0，

则从 A 中删除 A_i。 计算出梦梦将执行的操作总数。可以证明，无论梦梦如何选择 i 和 j，操作的总数是不变的。

第一行给出 1 个整数 N

第二行给出 N 个整数，第 i 个表示 Ai 。

一行一个整数，表示答案

样例1解释

梦梦将执行 3 次操作，如下所示：

1选择 i=3，j=1。梦梦得到A3=0 ，并从 A 中删除A3 。现在梦梦有 A=(2,3)。

2选择 i=2，j=1 。梦梦得到 A2=1。现在梦梦有 A=(2,1) 。

3选择 i=1，j=2。梦梦得到 A1=0，并从 A 中删除 A1。现在梦梦有  A=(1)，并终止操作，因为 A 的长度变为 1。

数据范围：

对于 30\% 的数据，满足 1\leq N \leq 20

对于 60\% 的数据，满足 1\leq N \leq 2000

对于 100\% 的数据，满足 1\leq N \leq 200000,1\leq A_i \leq 10^9