Codeforce：C. Mike and gcd problem

C. Mike and gcd problem

time limit per test 2 seconds memory limit per test 256 megabytes

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 ≤ 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

Copy

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.

思路：

思维和贪心经典题！详见代码

AC代码：

#include<stdio.h> const int maxn = 100010; int a[maxn], n; int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } int main() { int g, i; int odd = 0, even = 0; int ans = 0, flag = 0; scanf("%d", &n); for (i = 1; i <= n; ++i) { scanf("%d", &a[i]); if (i == 2) g = gcd(a[1], a[2]); else if (i > 2) g = gcd(g, a[i]); if (a[i] % 2 == 0) even++; else odd++; } if (g != 1) { printf("YES\n0\n"); return 0; } if (even == 0) { if (n & 1) printf("YES\n%d\n", n / 2 + 2); else printf("YES\n%d\n", n / 2); } else if (even != 0 && odd != 0) { flag = 0; for (i = 1; i <= n; i++) { if (a[i] % 2 != 0)flag++; else { if (flag & 1) ans = ans + (flag / 2 + 2); else ans = ans + flag / 2; flag = 0; } } if (flag != 0) { if (flag & 1) ans = ans + (flag / 2 + 2); else ans = ans + flag / 2; } printf("YES\n%d\n", ans); } return 0; }