题目描述

小高得到了一个长度为 $N$ 的正整数序列 $A=(A_1,A_2, \dots ,A_N)$。

他将重复执行以下操作，直到序列 $A$ 的长度变为 $1$：

• 设操作前 $A$ 的长度为 $k$。选择整数 $i$ 和 $j$，使得 $ \max(\{A_1,A_2,\dots,A_{k}\})=A_i,\min(\{A_1,A_2,\dots,A_{k}\})=A_j $，且 $i\ \neq\ j$。然后将 $A_i$ 替换为 $(A_i\ \bmod\ A_j)$。如果此时 $A_i$ 变为 $0$ ，则从 A 中删除 $A_i$。

请计算小高将执行的操作次数。可以证明，无论如何选择操作中的 $i$ 和 $j$，总操作次数都不会改变。

输入格式

输入从标准输入中给出，格式如下：

$N$

$A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出所求答案。

输入输出样例 #1

输入 #1

3
2 3 6

输出 #1

3

输入输出样例 #2

输入 #2

6
1232 452 23491 34099 57341 21488

输出 #2

12

说明/提示

样例 1 解释

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

1. 选择 $i=3,j=1$。得到 $A_3=0$，并从 $A$ 中删除 $A_3$。现在 $A=(2,3)$。
2. 选择 $i=2,j=1$。得到 $A_2=1$。现在 $A=(2,1)$。
3. 选择 $i=1,j=2$。得到 $A_1=0$，并从 $A$ 中删除 $A_1$。现在 $A=(1)$，由于 $A$ 的长度变为 $1$，终止操作。

数据范围

• $2\ \le\ N\ \le\ 2\ \times\ 10^5$
• $1\ \le\ A_i\ \le\ 10^9$
• 所有输入均为整数。