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,$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.

Input

Input is given from Standard Input in the following format:
N
$A_1 A_2 \dots A_N$

Output

Print the answer.

Constraints

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

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

见题面 Input 部分

见题面 Output 部分