题目描述

给定一个由 $N$ 个正整数组成的序列：$A=(A_1,A_2,\\dots,A_N)$。

你将执行以下操作，直到 $A$ 的长度变为 $1$。

• 设 $k$ 是此操作前的 $A$ 的长度。选择整数 $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 \\bmod A_j)$ 替换 $A_i$。如果此时 $A_i$ 变为 $0$，则从 $A$ 中删除 $A_i$。

求你将执行的操作次数。我们可以证明，无论在操作中如何选择 $i$ 和 $j$，操作的总次数都不会改变。

约束条件

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

输入

从标准输入读取输入数据，输入格式如下：

$N$

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

输出

输出答案。

示例输入1

3
2 3 6

示例输出1

3

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

• 选择 $i=3,j=1$。你得到 $A_3=0$，并从 $A$ 中删除 $A_3$。现在你有 $A=(2,3)$。
• 选择 $i=2,j=1$。你得到 $A_2=1$。现在你有 $A=(2,1)$。
• 选择 $i=1,j=2$。你得到 $A_1=0$，并从 $A$ 中删除 $A_1$。现在你有 $A=(1)$，并终止过程，因为 $A$ 的长度变为 $1$。

示例输入2

6
1232 452 23491 34099 57341 21488

示例输出2

12