题目描述

有 $N$ 张卡片，每张卡片上写有一个数值 $P_i$。

可以连接任意两张卡片，但需要花费 $\min(P_a\bmod P_b, P_b\bmod P_a)$。

请你求出连接所有卡片所需要的最小花费。

输入格式

第一行，一个整数 $N$，代表有 $N$ 张卡片；

接下来 $N$ 行，每行一个正整数 $P_i$，代表第 $i$ 张卡片上写的数值。

输出格式

一行，一个整数，代表最小花费。

4
2
6
3
11 

1

4
1
2
3
4 

0

3
4
9
15 

4

提示

【样例解释 #1】

连接卡片 $1$ 和卡片 $2$，花费 $\min(2\bmod 6,6\bmod 2)=0$；

连接卡片 $2$ 和卡片 $3$，花费 $\min(3\bmod 6,6\bmod 3)=0$；

连接卡片 $1$ 和卡片 $4$，花费 $\min(2\bmod 11,11\bmod 2)=1$。

总共花费 $0+0+1=1$。

【数据范围】

对于 $30\%$ 的数据，$1\le N\le 10^3$；

对于另外 $40\%$ 的数据，$1\le P_i\le 10^6$；

对于 $100\%$ 的数据，$1\le N\le 10^5$，$1\le P_i\le 10^7$。

【说明】

本题分值按 COCI 原题设置，满分 $140$。

题目译自 COCI2016_2017 CONTEST #6 T5 SIRNI