Mike has a sequence $*A* = [*a*_{1}, *a*_{2}, ..., *a*_{*n*}]$ of length $*n*$. He considers the sequence $*B* = [*b*_{1}, *b*_{2}, ..., *b*_{*n*}]$ 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 $*a*_{*i*}, *a*_{*i* + 1}$ and put numbers $*a*_{*i*} - *a*_{*i* + 1}, *a*_{*i*} + *a*_{*i* + 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 $*b*_{*i*}$ 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 $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ ($1 ≤ *a*_{*i*} ≤ 10^{9}$) — 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.

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