P7789 [COCI 2016/2017 #6] Sirni

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.

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.

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

**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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #6](https://hsin.hr/coci/archive/2016_2017/contest6_tasks.pdf) _**T5 SIRNI**_. Translated by ChatGPT 5