Tying All the Cards

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.

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$)

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

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.