如果一开始就满足题意，不用变换。
否则，如果对一对ai，ai+1用此变换，设新的gcd为d，则有（ai - ai+1）mod d = 0，（ai + ai+1）mod d = 0
变化一下就是2 ai mod d = 0
2 ai+1 mod d = 0
也就是说，用两次变换之后，gcd至少扩大2倍，于是，最优方案就是我们将所有的奇数都变成偶数。
只需要找出所有奇数段，答案就是sigma（[奇数段的长度/2]+(奇数段的长度 mod 2 ==1 ?)）。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
ll a[100010];
int main(){
// freopen("c.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%I64d",&a[i]);
}
int GCD=(int)a[1];
for(int i=2;i<=n;++i){
GCD=__gcd(GCD,(int)a[i]);
}
if(GCD!=1){
puts("YES
0");
return 0;
}
int cnt=0,sta;
for(int i=1;i<=n;++i){
if(a[i]%2ll==1 && (i==1 || a[i-1]%2ll==0)){
sta=i;
}
if(a[i]%2ll==1 && (i==n || a[i+1]%2ll==0)){
cnt+=(i-sta+1)/2+((i-sta+1)%2==1 ? 2 : 0);
}
}
printf("YES
%d
",cnt);
return 0;
}