Problem Description

There are $N$ cards, each card has a value $P_i$ written on it.

You can connect any two cards, but it costs $\min(P_a \bmod P_b, P_b \bmod P_a)$.

Please find the minimum cost to connect all the cards.

Input Format

The first line contains an integer $N$, representing the number of cards.

The next $N$ lines each contain a positive integer $P_i$, representing the value written on the $i$-th card.

Output Format

A single line containing an integer, representing the minimum cost.

Sample Input and Output

Sample Input #1

4
2
6
3
11

Sample Output #1

1

Sample Input #2

4
1
2
3
4

Sample Output #2

0

Sample Input #3

3
4
9
15

Sample Output #3

4

Notes

[Sample Explanation #1]

Connecting card $1$ and card $2$ costs $\min(2 \bmod 6, 6 \bmod 2) = 0$.

Connecting card $2$ and card $3$ costs $\min(3 \bmod 6, 6 \bmod 3) = 0$.

Connecting card $1$ and card $4$ costs $\min(2 \bmod 11, 11 \bmod 2) = 1$.

The total cost is $0 + 0 + 1 = 1$.

[Data Range]

For $30\%$ of the data, $1 \le N \le 10^3$.

For another $40\%$ of the data, $1 \le P_i \le 10^6$.

For $100\%$ of the data, $1 \le N \le 10^5$, $1 \le P_i \le 10^7$.

[Notes]

This problem is scored according to the original COCI settings, with a full score of $140$.

The problem is translated from COCI2016_2017 CONTEST #6 T5 SIRNI.

见题面 Input 部分

见题面 Output 部分