Tying All the Cards

Time limit5sMemory limit768 MB

Summary

Tie all N cards into one connected set where each tie costs the larger number modulo the smaller, with minimum total cost.

Level: Hard8 of 10
Topics: Minimum spanning tree, Number theory, Union-find
Solved: No attempts yet

Problem

Daniel has a bag of candy and $N$ cards. Each card has one positive integer $P_i$ written on it.

While eating his candy, Daniel thought of a game. He can tie together two cards labelled $a$ and $b$ , and each tie forces him to eat $\min(a \bmod b,\ b \bmod a)$ pieces of candy, where $x \bmod y$ is the remainder of $x$ divided by $y$ .

Daniel wants to tie the cards so that lifting any one card lifts all the others with it. A single card can be tied directly to any number of other cards. Daniel watches his figure, so he does not want to eat much.

Compute the smallest number of candy pieces he must eat to connect all the cards.

Input

The first line contains the positive integer $N$ . ( $1 \le N \le 10^5$ )

Each of the next $N$ lines contains one positive integer $P_i$ written on a card. ( $1 \le P_i \le 10^7$ )

Output

Print on the first line the smallest number of candy pieces needed to connect all the cards.

Hint

In the first example Daniel ties the first card to the second and eats 0 candy, ties the second card to the third and eats 0 candy, then ties the first card to the fourth and eats 1 candy. One piece of candy connects all four cards.

Examples3

Example 1
Input
```
4
2
6
3
11
```
Expected output
```
1
```
Example 2
Input
```
4
1
2
3
4
```
Expected output
```
0
```
Example 3
Input
```
3
4
9
15
```
Expected output
```
4
```