CF798C.Mike and gcd problem

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

Mike 有一个长度为 $ n $ 的序列 $ A = [a_1, a_2, \dots, a_n] $。他称一个序列 $ B = [b_1, b_2, \dots, b_n] $ 是优美的，当且仅当该序列所有元素的最大公约数大于 1，即
。

Mike 希望通过修改他的序列，使其变为优美的。在一次操作中，他可以选择一个下标 $ i $（满足 $ 1 \le i < n $），删除 $ a_i $ 和 $ a_{i+1} $，并按顺序在原位置插入两个新数：$ a_i - a_{i+1} $ 和 $ a_i + a_{i+1} $。他希望执行尽可能少的操作。请找出使序列 $ A $ 变为优美的最少操作次数；若不可能，请说明无法实现。

是最大的非负整数 $ d $，使得对每个 $ i $（$ 1 \le i \le n $）都有 $ d \mid b_i $。

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.

第一行包含一个整数 $n$（$2 \leq n \leq 100\,000$）——序列 $A$ 的长度。

第二行包含 $n$ 个以空格分隔的整数 $a_1,\,a_2,\,...,\,a_n$（$1 \leq a_i \leq 10^9$）——序列 $A$ 的元素。

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.

如果可以通过执行上述操作使序列 A 变为优美序列，则在第一行输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。

如果答案为 "YES"，则输出使序列 A 变为优美序列所需的最少操作次数。

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.

在第一个例子中，你只需执行一次操作即可得到序列 [0, 2]，其结果为 。

在第二个例子中，该序列的 gcd 已经大于 1。