← 返回题目列表

Codeforces · 1305/F

F. 库罗尼和惩罚

中文机器翻译题面 查看原题

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$$$,因此该数组将是好的。可以证明,三个或更少的操作序列都不能使数组变得良好。