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.