问题 CH: 麦克和公约数问题

内存限制：256 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：24 通过：4

Mike有一个长度为n的序列A=[a1，a2，…，an]。他认为一个序列 B=[b1,b2,…,bn] 是优美的，当且仅当其所有元素的 gcd⁡大于 1，即 gcd(b1,b2,…,bn)>1。

迈克想改变他的顺序，让它变得优美。在一个步骤中，他可以选择索引i（1≤i＜n），删除数字 a_i,a_i+1，并按顺序将数字a_i- a_i+1,a_i+ a_i+1放在其位置。他希望操作次数尽可能少。如果序列可以变为优美的，你需要给出最少操作次数，否则，指出不可能。

gcd(b1,b2,…,bn) 是最大的非负整数 d 使得d 整除每一个bi(1⩽i⩽n),即最大公约数。

第一行包含单个整数n（2≤n≤100000) − 序列A的长度。

第二行包含n个空格分隔的整数a₁,a₂,...,a_n (1≤a_i≤10⁹) − 序列A的元素。

如果可以通过执行上述操作使序列A变美，则在第一行输出“YES”（不带引号），否则输出“NO”（不含引号）。

如果答案是“YES”，则输出使序列A漂亮所需的最少移动次数。

Examples

Input

2
1 1

Output

YES
1

Input

3
6 2 4

Output

YES
0

Input

2
1 3

Output

YES
1

注意
在第一个示例中，您只需执行一次移动即可使用获取序列 [0，2]。
在第二个示例中，序列的 gcd 已经大于 1。

2
1 1

YES
1