本文共 1971 字，大约阅读时间需要 6 分钟。

Mike has a sequence A = [a1, a2, …, an] of length n. He considers the sequence B = [b1, b2, …, bn] beautiful if the gcd of all its elements is bigger than 1, i.e. .

Mike wants to change his sequence in order to make it beautiful. In one move he can choose an index i (1 ≤ i < n), delete numbers ai, ai + 1 and put numbers ai - ai + 1, ai + ai + 1 in their place instead, in this order. He wants perform as few operations as possible. Find the minimal number of operations to make sequence A beautiful if it’s possible, or tell him that it is impossible to do so.

is the biggest non-negative number d such that d divides bi for every i (1 ≤ i ≤ n).

Input

The first line contains a single integer n (2 ≤ n ≤ 100 000) — length of sequence A.

The second line contains n space-separated integers a1, a2, …, an (1 ≤ ai ≤ 109) — elements of sequence A.

Output

Output on the first line “YES” (without quotes) if it is possible to make sequence A beautiful by performing operations described above, and “NO” (without quotes) otherwise.

If the answer was “YES”, output the minimal number of moves needed to make sequence A beautiful.

Examples

Input 2 1 1 Output YES 1 Input 3 6 2 4 Output YES 0 Input 2 1 3 Output YES 1 Note In the first example you can simply make one move to obtain sequence [0, 2] with .

In the second example the gcd of the sequence is already greater than 1.

题意：给定一组序列，通过若干次变化是指成为一个美丽的序列。美丽序列的定义是，数组中所有数字的最大公因数大于1。问是否能转换成这样的一个序列，并且最少的变换次数是多少。 思路：一定可以转换成。 如果这个序列一开始就是最大公因数大于1，那么就不需要变换。如果不是的话，就有这样的几种情况。奇奇，偶偶，奇偶，偶奇。对于偶偶来说，不用管。对于其他三种情况来说 ①奇奇：转换成偶偶，只需要一步。 ②奇偶，偶奇：转换成偶偶需要两步。 因为求最少的步数，所以我们应该应该多转换奇奇，其次是奇偶，偶奇。 所以我们先找数组中的奇奇，然后再找奇偶，或者偶奇。 代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=1e5+100;int a[maxx];int n;int main(){
   	scanf("%d",&n);	scanf("%d",&a[1]);	int cnt=a[1];	for(int i=2;i<=n;i++) 	{
   		scanf("%d",&a[i]);		cnt=__gcd(cnt,a[i]);	}	ll sum=0;	if(cnt>1) 	{
   		cout<<"YES"<
    
     <
     
      <
     
    
   

努力加油a啊，(^o)/~

转载地址：http://oytvi.baihongyu.com/