Fox and Number Game

1000ms

262144K

Description:

Fox Ciel is playing a game with numbers now.

Ciel has n positive integers: x₁, x₂, ..., x_n. She can do the following operation as many times as needed: select two different indexes i and j such that x_i > x_j hold, and then apply assignment x_i = x_i - x_j. The goal is to make the sum of all numbers as small as possible.

Please help Ciel to find this minimal sum.

Input:

The first line contains an integer n (2 ≤ n ≤ 100). Then the second line contains n integers: x₁, x₂, ..., x_n (1 ≤ x_i ≤ 100).

Output:

Output a single integer — the required minimal sum.

Sample Input:

2
1 2

Sample Output:

Sample Input:

3
2 4 6

Sample Output:

Sample Input:

2
12 18

Sample Output:

Sample Input:

5
45 12 27 30 18

Sample Output:

Note:

In the first example the optimal way is to do the assignment: x₂ = x₂ - x₁.

In the second example the optimal sequence of operations is: x₃ = x₃ - x₂, x₂ = x₂ - x₁.

Informação

Provedor Codeforces

Código CF389A