题目描述

小高得到了一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,...,A_N)$。
他将重复执行以下操作，直到序列 $A$ 的长度变为 $1$：

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

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

输入格式

输入从标准输入中给出，格式如下：
$N$
$A_1$ $A_2$ ... $A_N$

输出格式

输出所求答案。

样例

3
2 3 6

3

6
1232 452 23491 34099 57341 21488

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 ≤ N ≤ 2 × 10^5$
$1 ≤ A_i ≤ 10^9$
所有输入均为整数。

来源

• AtCoder ARC147A