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。