#P18868. [HONI 2016/2017 #6] Sirni

[HONI 2016/2017 #6] Sirni

题目描述

有 NN 张卡片,第 ii 张写有正整数 PiP_i。用一根丝带连接卡片 a,ba,b,需要吃掉 min⁡(Pa mod Pb,Pb mod Pa)\min(P_a\bmod P_b,P_b\bmod P_a) 颗糖。

可以连接任意两张不同的卡片,每张卡片可以和多张别的卡片相连。求把所有卡片连成一个整体所需吃掉的最少糖果数。

输入格式

第一行一个整数 NN,满足 1≤N≤1051\le N\le10^5。接下来 NN 行,每行一个整数 PiP_i,满足 1≤Pi≤1071\le P_i\le10^7。

输出格式

输出最少需要吃掉的糖果数。

部分分

30%30\% 的分值对应 N≤103N\le10^3 的测试;另有 40%40\% 的分值对应所有 Pi≤106P_i\le10^6 的测试。

样例

样例 1

输入

4
2
6
3
11

输出

1

样例 2

输入

4
1
2
3
4

输出

0

样例 3

输入

3
4
9
15

输出

4