Kuroni 对其他二传手使用他作为主题非常生气!作为惩罚,他强迫他们解决以下问题:
您有一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。操作包括选择一个元素并向其添加 $$$1$$$ 或从中减去 $$$1$$$,以使该元素保持正数。如果数组所有元素的最大公约数不是 $$$1$$$,我们就说这个数组是好的。求出使数组良好所需的最少操作数。
由于无法与 Kuroni 的智力相匹配,二传手未能解决问题。帮助他们逃脱库洛尼的惩罚!
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组中的元素数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$。 ($$$1 \le a_i \le 10^{12}$$$) — 数组的元素。
输出
打印单个整数 - 使数组良好所需的最少操作数。
示例
输入 #1
3 6 2 4
输出 #1
0
输入 #2
5 9 8 7 3 1
输出 #2
4
注意
在第一个示例中,第一个数组已经很好,因为所有元素的最大公约数是 $$$2$$$。
在第二个示例中,我们可以应用以下操作:
1. 将 $$$1$$$ 添加到第二个元素,使其等于 $$$9$$$。
2. 从第三个元素中减去$$$1$$$,使其等于$$$6$$$。
3. 将$$$1$$$ 添加到第五个元素,使其等于$$$2$$$。
4. 再次将 $$$1$$$ 添加到第五个元素,使其等于 $$$3$$$。
所有元素的最大公约数将等于 $$$3$$$,因此该数组将是好的。可以证明,三个或更少的操作序列都不能使数组变得良好。