Description

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

You may connect any two cards, but the cost is $\min(P_a\bmod P_b, P_b\bmod P_a)$.

Please find the minimum total cost to connect all cards.

Input Format

The first line contains an integer $N$, meaning there are $N$ cards.

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

Output Format

One line containing one integer, representing the minimum total cost.

4
2
6
3
11 

1

4
1
2
3
4 

0

3
4
9
15 

4

Hint

Sample Explanation #1

Connect card $1$ and card $2$, the cost is $\min(2\bmod 6,6\bmod 2)=0$.

Connect card $2$ and card $3$, the cost is $\min(3\bmod 6,6\bmod 3)=0$.

Connect card $1$ and card $4$, the cost is $\min(2\bmod 11,11\bmod 2)=1$.

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

Constraints

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

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

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

Notes

The score of this problem follows the original COCI settings, with a full score of $140$.

Translated from COCI2016_2017 CONTEST #6 T5 SIRNI.

Translated by ChatGPT 5