Mike has a sequence A?=?[a₁,?a₂,?...,?a_n] of length n. He considers the sequence B?=?[b₁,?b₂,?...,?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₁,?a₂,?...,?a_n (1?≤?a_i?≤?10⁹) — 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.

Example

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.

第一行一個(gè)n，代表n個(gè)數(shù)字輸入，第二行輸入數(shù)字，你可以對(duì)第i個(gè)數(shù)和第i+1執(zhí)行一種交換操作，即用a_i,?a_i?+?1?替代a_i?-?a_i?+?1,?a_i?+?a_i?+?1

求最少進(jìn)行多少次操作，能使該序列的最大公共公因數(shù)>1，這里題目是絕對(duì)有解的，不需考慮no的情況

對(duì)于數(shù)字a，b進(jìn)行操作：? a,b ? a-b,a+b? -2b,2a

由此題目就容易了，2是最容易想到的最大公因數(shù)，而進(jìn)行操作又可以令無論奇偶的兩個(gè)數(shù)都變成偶數(shù)

那么對(duì)數(shù)組進(jìn)行訪問

1.假如第i個(gè)數(shù)和第i+1個(gè)數(shù)都為偶數(shù)，操作次數(shù)為0（不產(chǎn)生影響，不用判斷）

2.假如第i個(gè)數(shù)和第i+1個(gè)數(shù)都為奇數(shù)，操作次數(shù)為1

3.假如一個(gè)奇數(shù)一個(gè)偶數(shù)，操作次數(shù)為2

但這里就有一個(gè)問題了，2和3之間存在沖突，并且2幾乎無法觸發(fā)。而題目求的是最少操作數(shù)量，那么顯然2是優(yōu)于3的，所以在處理時(shí)應(yīng)給2更高的優(yōu)先級(jí)。因此可以對(duì)數(shù)組進(jìn)行兩次訪問，第一次執(zhí)行操作2，第二次執(zhí)行操作3。

另外，題目有一個(gè)要注意的地方是在交換前最大公共公因數(shù)已經(jīng)符合條件的話，可以直接結(jié)束，代碼如下

#include<stdio.h> #define MAX 100000 int gcd(int s1,int s2) {int r;while (s2!=0) {r=s1%s2;s1=s2;s2=r;}return s1; } int main() {int n,i,j,a[MAX],t,ans;while(scanf("%d",&n)!=EOF){t=0;for(i=1;i<=n;i++){scanf("%d",&a[i]);}ans=gcd(a[1],a[2]);for(i=3;i<=n;i++)ans=gcd(ans,a[i]);if(ans>1)printf("YES\n0\n");else{?ans=0;for(i=2;i<=n;i++){if(a[i-1]%2&&a[i]%2){ans++;a[i-1]=0;a[i]=0;}}for(i=2;i<=n;i++){if(a[i-1]%2==0&&a[i]%2||a[i-1]%2&&a[i]%2==0){ans+=2;a[i-1]=0;a[i]=0;}}printf("YES\n%d\n",ans);}} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/qq936584671/p/6814876.html

總結(jié)

以上是生活随笔為你收集整理的CodeForces798cMike and gcd problem的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。