← 返回题目列表

Codeforces · 798/C

C. 迈克和gcd问题

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

Mike 有一个长度为 n 的序列 A = [a1, a2, ..., an]。如果序列 B = [b1, b2, ..., bn] 所有元素的 gcd 都大于 1,即 $${ \operatorname* { g c d } } ( b _ { 1 }, b _ { 2 }, \ldots, b _ { n } ) > 1$$,则他认为序列 B = [b1, b2, ..., bn] 是美丽的。

迈克想要改变他的序列以使其变得漂亮。在一步操作中,他可以选择一个索引 i (1 ≤ i < n),删除数字 ai、ai + 1 并按顺序将数字 ai - ai + 1、ai + ai + 1 放在原来的位置。他希望执行尽可能少的操作。如果可能的话,找出使序列 A 变得漂亮的最少操作次数,或者告诉他这是不可能的。

$$\gcd(b_{1},b_{2},\ldots,b_{n})$$ 是最大的非负数 d,使得 d 对每个 i (1 ≤ i ≤ n) 整除 bi。

输入

第一行包含一个整数 n (2 ≤ n ≤ 100 000) — 序列 A 的长度。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 序列 A 的元素。

输出

如果通过执行上述操作可以使序列 A 变得漂亮,则在第一行输出“YES”(不带引号),否则输出“NO”(不带引号)。

如果答案为“是”,则输出使序列 A 漂亮所需的最少步数。

示例

输入 #1

2
1 1

输出 #1

YES
1

输入 #2

3
6 2 4

输出 #2

YES
0

输入 #3

2
1 3

输出 #3

YES
1

注意

在第一个示例中,您只需移动一步即可通过 $$\gcd(0, 2) = 2$$ 获得序列 [0, 2]。

在第二个示例中,序列的 gcd 已经大于 1。