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. <image>. 

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.

<image> 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 <image>.

In the second example the gcd of the sequence is already greater than 1. 
import java.io.*;
import java.util.*;

public class mikegcd
{
	static Scanner sc=new Scanner(System.in);
	static PrintWriter pw=new PrintWriter(System.out,true);
	static int inf=(1<<30);
	static int min(int x,int y)
	{
		return (x<y?x:y);
	}
	static long _gcd(long a,long b)
	{
		if (b==0)
			return a;
		return _gcd(b,a%b);
	}
	static long gcd(long a,long b)
	{
		return _gcd(Math.abs(a),Math.abs(b));
	}
	static long a[]=new long[100010];
	static int dp[][]=new int[100010][2];
	static int n;
	static int doit(int c,int f)
	{
		if (c>n)
			return (f==0?0:(1<<28));
		if (dp[c][f]!=-1)
			return dp[c][f];
		int ret=0;
		if (f==1)
		{
			ret=(a[c]%2==1?1:2)+doit(c+1,0);
		}
		else
		{
			ret=(a[c]%2==1?2:0)+doit(c+1,0);
			if (a[c]%2==1)
			{
				ret=min(ret,doit(c+1,1));
			}
		}
		return dp[c][f]=ret;
	}
	public static void main(String args[])
	{
		
		
		int i,j;
		n=sc.nextInt();
		for (i=1;i<=n;i++){
			a[i]=(int)sc.nextInt();
			//b[i]=a[i];
			dp[i][0]=dp[i][1]=-1;
		}
		int ini=0;
		ini+=doit(2,(int)a[1]%2);
		long g=a[1],gg=0;
		int f=1,ans=0;
		for (i=2;i<=n;i++){
			if (gcd(g,a[i])==1)
			{
				int c=0;
				//pw.println("entered in contro : with g:"+g+" and gg:"+gg);
				while  (gcd(gg,gcd(a[i-1],a[i]))==1&&c<16){
					long x=a[i-1],y=a[i];
					a[i-1]=x-y;
					a[i]=x+y;
					c++;
					ans++;
					///pw.println(a[i-1]+" "+a[i]+" ");

				}
				if (gcd(gg,gcd(a[i-1],a[i]))==1)
				{
					f=0;
					break;
				}
			}
			if (f==0)
				break;
			gg=g;
			g=gcd(g,a[i]);

		}
		{
			pw.println("YES");
			pw.println(min(ini,(f==1?ans:(1<<30))));
		}
	}
}