Mike has a sequence *A* = [*a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>] of length *n*. He considers the sequence *B* = [*b*<sub class="lower-index">1</sub>, *b*<sub class="lower-index">2</sub>, ..., *b*<sub class="lower-index">*n*</sub>] beautiful if the *gcd* of all its elements is bigger than 1, i.e. <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/1829934399ec1245c6050a62cf6e36810163b03b.png" style="max-width: 100.0%;max-height: 100.0%;"/>. 

Mike wants to change his sequence in order to make it beautiful. In one move he can choose an index *i* (1 ≤ *i* &lt; *n*), delete numbers *a*<sub class="lower-index">*i*</sub>, *a*<sub class="lower-index">*i* + 1</sub> and put numbers *a*<sub class="lower-index">*i*</sub> - *a*<sub class="lower-index">*i* + 1</sub>, *a*<sub class="lower-index">*i*</sub> + *a*<sub class="lower-index">*i* + 1</sub> 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.

<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/69b4319fc56f0d760506d7f84e7647ff65f6bdc5.png" style="max-width: 100.0%;max-height: 100.0%;"/> is the biggest non-negative number *d* such that *d* divides *b*<sub class="lower-index">*i*</sub> for every *i* (1 ≤ *i* ≤ *n*).
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*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — elements of sequence *A*.
In the first example you can simply make one move to obtain sequence [0, 2] with <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/6ddb490b8e898198d30c56c6edce2cf15e6f998a.png" style="max-width: 100.0%;max-height: 100.0%;"/>.

In the second example the *gcd* of the sequence is already greater than 1.
2
1 1
YES
1
3
6 2 4
YES
0
2
1 3
YES
1
9
57 30 28 81 88 32 3 42 25
YES
8
2
8 77
YES
2
4
92 46 3 21
YES
1
2
78 26
YES
0
2
3 6
YES
0
2
3 9
YES
0
2
3 3
YES
0
3
3 6 3
YES
0
3
3 9 15
YES
0
3
3 6 9
YES
0
3
3 3 3
YES
0
3
3 9 18
YES
0
5
1 2 1 2 1
YES
6
2
9 6
YES
0
4
3 6 9 12
YES
0
3
3 9 27
YES
0
3
3 9 12
YES
0
5
6 6 9 15 21
YES
0
2
5 15
YES
0
4
2 3 9 13
YES
3
4
3 3 3 3
YES
0
5
3 9 9 9 27
YES
0
2
9 9
YES
0
3
3 9 9
YES
0
3
7 14 21
YES
0
3
3 12 4
YES
2
5
3 3 3 3 3
YES
0
import sys

input = sys.stdin.readline


############ ---- Input Functions ---- ############
def inp():
    return (int(input()))


def inlt():
    return (list(map(int, input().split())))


def insr():
    s = input()
    return (list(s[:len(s) - 1]))


def invr():
    return (map(int, input().split()))


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def main():
    n = inp()

    a = inlt()

    g = 0
    for i in range(n):
        g = gcd(g, a[i])

    if g > 1:
        print('YES')
        return 0
    res = 0

    for i in range(n - 1):
        if a[i]%2 == 1 and a[i+1] % 2 == 1:
            res += 1
            a[i] = 2
            a[i + 1] = 2

    for i in range(n):
        if a[i]%2 == 1:
            res += 1
    print('YES')
    return res

print(main())