題干：

You have an array?a?with length?n, you can perform operations. Each operation is like this: choose two?adjacent?elements from?a, say?x?and?y, and replace one of them with?gcd(x,?y), where?gcd?denotes the?greatest common divisor.

What is the minimum number of operations you need to make all of the elements equal to?1?

Input

The first line of the input contains one integer?n?(1?≤?n?≤?2000) — the number of elements in the array.

The second line contains?n?space separated integers?a1,?a2,?...,?an?(1?≤?ai?≤?109)?— the elements of the array.

Output

Print?-1, if it is impossible to turn all numbers to?1. Otherwise, print the minimum number of operations needed to make all numbers equal to?1.

Examples

Input

5 2 2 3 4 6

Output

5

Input

4 2 4 6 8

Output

-1

Input

3 2 6 9

Output

4

Note

In the first sample you can turn all numbers to?1?using the following?5?moves:

• [2,?2,?3,?4,?6].
• [2,?1,?3,?4,?6]
• [2,?1,?3,?1,?6]
• [2,?1,?1,?1,?6]
• [1,?1,?1,?1,?6]
• [1,?1,?1,?1,?1]

We can prove that in this case it is not possible to make all numbers one using less than?5?moves.

題目大意：

? ?給你一組數，定義一個操作：每次可以選擇相鄰的兩個并且把其中一個的值變成他倆的gcd，，求問多少次操作后可以把這組數變成全1的、

給你一個長度為n的數組a。每次操作你可以選擇相鄰的兩個位置a[i],a[i+1]，將其中某一個數用gcd(a[i],a[i+1])來代替。
你的目標是最后將a中所有元素都變成1，問最少需要多少次操作。如果無論怎樣最后a數組不能全變成1，那么輸出-1

解題報告：

? 看數據量，o(n^2)暴力就好了。。首先湊出一個1，然后剩下的次數就是剩下不是1的個數了。。

? ?這樣構造的正確性想想就出來了。。其實也不難想，，因為你每次操作最多就改變一個數嘛、、假設就算這些數全是互質的，那也就是相當于先挑任意倆個來湊出個1，然后再去更新其他值嘛，，所以和直接看1的個數是一樣的，，所以這題的關鍵點在于找1，而不是找互質的兩個數。

貼一個題解：當序列中有1時，則gcd(1,s[i])最優。如果沒有1，要湊出一個1.?
gcd(gcd(a,b),gcd(b,c))=gcd(gcd(a,b),c)=gcd(a,gcd(b,c))

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const int INF = 0x3f3f3f3f; int a[MAX]; int main() {int t,cnt=0,n;int minn = INF;cin>>n;for(int i = 1; i<=n; i++) {scanf("%d",a+i);if(a[i] == 1) cnt++;}if(cnt!=0) {printf("%d\n",n-cnt);return 0 ;}int g;for(int i = 1; i<n; i++) {g=a[i];for(int j = i+1; j<=n; j++) {g=__gcd(g,a[j]);if(g==1) {minn = min(minn,j-i+n-1);//相當于先湊出這個1用了j-i,然后相當于cnt=1的上面那種情況，用n-cnt步來湊出答案。break;}}}if(minn == INF) puts("-1");else printf("%d\n",minn);return 0 ;}

?

總結

以上是生活随笔為你收集整理的【CodeForces - 892C 】Pride （数学，思维构造，gcd）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。