On the eve of the Spring Festival, Mickey found a repeater on the clock tower. This repeater can not only repeat audio automatically but can also be used to find the greatest common divisor of all numbers in a sequence.

The machine is used as follows: initially, input a sequence of length $n$, where the $i$-th number is $a_i$ ($1 \le i \le n$).

Each time, Mickey can choose two adjacent numbers $a_i$ and $a_{i+1}$ and insert a number of gold coins exactly equal to the sum of these two numbers, i.e., $a_i + a_{i+1}$, into the machine. The machine then automatically calculates the greatest common divisor of these two numbers and replaces the two adjacent numbers with this result at their original position. This operation is repeated until only one number remains in the machine, which is the answer.

As the saying goes, a wealthy mouse who doesn't want to be a repeater repairman is not a good mathematician. Mickey wants to know the minimum number of gold coins required to calculate the answer.

Input

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

The second line contains $n$ positive integers $a_i$, representing the sequence.

Output

A single integer representing the minimum number of gold coins used.

Examples

Input 1

7
33 33 66 6 66 22 22

Output 1

260

Note 1

Initially, the sequence is $[33, 33, 66, 6, 66, 22, 22]$.

Step 1: Merge $a_4, a_5$ to get $[33, 33, 66, 6, 22, 22]$.

Step 2: Merge $a_4, a_5$ to get $[33, 33, 66, 2, 22]$.

Step 3: Merge $a_3, a_4$ to get $[33, 33, 2, 22]$.

Step 4: Merge $a_2, a_3$ to get $[33, 1, 22]$.

Step 5: Merge $a_1, a_2$ to get $[1, 22]$.

Step 6: Merge $a_1, a_2$ to get $[1]$.

The total cost is $(6 + 66) + (6 + 22) + (66 + 2) + (33 + 2) + (33 + 1) + (1 + 22) = 260$.

Input 2

See sample data download.

Constraints

For all data, it is guaranteed that $1\le n\le 2\times 10^5$ and $1\le a_i \le 10^{12}$.