Array Zeroing

Problem Description

Little A has an array $a = [a_1, a_2, \ldots, a_n]$ consisting of $n$ non-negative integers. He repeatedly applies the following operation to the array $a$ until it contains only zeros. In one operation, Little A does the following three steps in order:

1. Find the largest integer in the array $a$, and let its index be $k$. If there are several maximum values, choose the one with the largest index.
2. Among all non-zero integers in the array $a$, find the smallest integer $a_j$.
3. Subtract $a_j$ from the $a_k$ found in step 1.

For example, the array $a = [2, 3, 4]$ needs $7$ operations to become $[0, 0, 0]$:

$$[2, 3, 4] \rightarrow [2, 3, 2] \rightarrow [2, 1, 2] \rightarrow [2, 1, 1] \rightarrow [1, 1, 1] \rightarrow [1, 1, 0] \rightarrow [1, 0, 0] \rightarrow [0, 0, 0]$$

Little A wants to know, for a given array $a$, how many operations are needed to turn all its elements into $0$. It can be proved that the elements of $a$ will all become $0$ after a finite number of operations. Can you compute the answer for him?

Input Format

The first line contains a positive integer $n$, the length of the array $a$.

The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$, the elements of the array.

Output Format

One line, a positive integer: the number of operations needed to turn all elements of $a$ into $0$.

Sample Input 1

3
2 3 4

Sample Input 2

5
1 3 2 2 5

Sample Output 1

7

Sample Output 2

13

Sample Explanation

For the first sample, the array is $[2, 3, 4]$, and the operations proceed as follows:

1. Maximum is $4$ (index $3$), smallest non-zero is $2$, $4 - 2 = 2$, array becomes $[2, 3, 2]$.
2. Maximum is $3$ (index $2$), smallest non-zero is $2$, $3 - 2 = 1$, array becomes $[2, 1, 2]$.
3. Maximum is $2$ (several maxima; choose the largest index, i.e. the last $2$), smallest non-zero is $1$, $2 - 1 = 1$, array becomes $[2, 1, 1]$.
4. Maximum is $2$, smallest non-zero is $1$, $2 - 1 = 1$, array becomes $[1, 1, 1]$.
5. Maximum is $1$ (choose the largest index, i.e. the third $1$), smallest non-zero is $1$, $1 - 1 = 0$, array becomes $[1, 1, 0]$.
6. Maximum is $1$ (index $2$), smallest non-zero is $1$, $1 - 1 = 0$, array becomes $[1, 0, 0]$.
7. Maximum is $1$ (index $1$), smallest non-zero is $1$, $1 - 1 = 0$, array becomes $[0, 0, 0]$.

After $7$ operations in total, everything becomes $0$.

Constraints

For all test cases, $1 \leq n \leq 100$, $0 \leq a_i \leq 100$.