Codeforces Round 410 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

greedy

number theory

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Mike and gcd problem

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMike 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.

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 02:41:00 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|