LGTB 得到了一个序列，他想在这个序列中选择一个最长的连续子序列，使得这个子序列的最大公约数等于

1。请告诉他他能得到的最大长度，如果没有这样的序列，输出?1

输入

输入第一行包含一个整数n 代表序列大小

接下来一行，包含n 个整数a1, a2, ..., an，代表序列

对于50% 的数据，1 n 1000

对于100% 的数据，1 n 105 1 ai 109

输出

输出包含一个整数l，代表最长的连续子序列，如果无解请输出?1

样例

样例输入      样例输出

2               2

7 2

样例输入      样例输出

3               -1

2 2 4

 

找规律，若存在子序列最大公因数为1，则最大子序列就是原序列总长。

所以只用判断原序列是否满足，依次gcd。注意特判n=1(虽然我觉得这不可能，因为n=1不存在公因数，但数据有2个都是n=1。。)

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int maxn=100005; 8 int a[maxn]; 9 int n;10 int gcd(int x,int y)11 {12     if(y==0)return x;13     return gcd(y,x%y);14 }15 int main()16 {17     freopen("seq.in","r",stdin);18     freopen("seq.out","w",stdout);19     scanf("%d",&n);20     for(int i=1;i<=n;i++)21     scanf("%d",&a[i]);22     if(n==1&&a[1]==1)23     {24         printf("1");25         return 0;26     }27     int k=a[1];28     int temp=1;29     while(temp