Problem Statement

You are given a sequence of $N$ positive integers: $A=(A_1,A_2,\\dots,A_N)$.

You will repeat the following operation until the length of $A$ becomes $1$.

• Let $k$ be the length of $A$ before this operation. Choose integers $i$ and $j$ such that $\\max(\\{A_1,A_2,\\dots,A_{k}\\})=A_i,\\min(\\{A_1,A_2,\\dots,A_{k}\\})=A_j$, and $i \\neq j$. Then, replace $A_i$ with $(A_i \\bmod A_j)$. If $A_i$ becomes $0$ at this moment, delete $A_i$ from $A$.

Find the number of operations that you will perform. We can prove that, no matter how you choose $i,j$ in the operations, the total number of operations does not change.

Constraints

• $2 \\le N \\le 2 \\times 10^5$
• $1 \\le A_i \\le 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3
2 3 6

Sample Output 1

3

You will perform $3$ operations as follows:

• Choose $i=3,j=1$. You get $A_3=0$, and delete $A_3$ from $A$. Now you have $A=(2,3)$.
• Choose $i=2,j=1$. You get $A_2=1$. Now you have $A=(2,1)$.
• Choose $i=1,j=2$. You get $A_1=0$, and delete $A_1$ from $A$. Now you have $A=(1)$, and terminate the process because the length of $A$ becomes $1$.

Sample Input 2

6
1232 452 23491 34099 57341 21488

Sample Output 2

12