from math import*
H=abs
E=enumerate
def C(s,c=[]):
 if[]==s and c:yield c;return
 if s:yield from[*C(s[1:],c+[s[0]]),*C(s[1:],c)]
I=lambda V,i:{(0,V),(V//i,V%i)}
def W(x,y):
 t=[[x,1,0],[y,0,1]]
 while t[-1][0]:q=t[-2][0]//t[-1][0];t+=[t[-2][0]%t[-1][0],t[-2][1]-q*t[-1][1],t[-2][2]-q*t[-1][2]],
 return t[-2]
def D(a,b,x,y,g):
 q=[(0,1,x,y),(0,-1,x,y)]
 while q:
  m,d,X,Y=q.pop(0);m+=d
  if all([X,Y]):yield(X,Y)
  J,K=x+m*(b/g),y-m*(a/g);q+=[(m,d,J,K)]*(H(X)+H(Y)>H(J)+H(K)or 1>all([X,Y]))
def f(s):
 for O in range(1,len(s)):
  for J in sorted(C([*E(s)][:O][::-1]),key=len):
   if~-len(J):
    q=[(J[0][1],[(1,J[0])],J[1:],s[O])]
    while q:
     x,R,S,v=q.pop(0)
     if S:
      y=S[0][1]
      for i in range(v-1):
       if(v-i)%gcd(x,y)<1:g,a,b=W(X:=max(x,y),Y:=min(x,y));G=(v-i)//g;A,B=min(D(X,Y,[b,a][x>y]*G,[a,b][x>y]*G,g),key=lambda x:sum(map(H,x)));q+=(v-i,[(A*z,l)for z,l in R]+[(B,S[0])],S[1:],i),
     else:
      for u in I(v,O+1):yield([R,*u],O)
   else:
    yield([0,s[O]//-~O,s[O]%-~O],O)
    for u in I(s[O]%J[0][1],O+1):j=s[O]//J[0][1];yield([[(1,J[0])for _ in range(j)],*u],O);yield([[(j,J[0])],*u],O)
def F(s):
 for i in f(s):
  e,W=i
  if all([[(a==sum(N*s[i+~W+I]for N,(I,_)in e[0])+i*e[1]+e[2]for i,a in E(s,1)if i>max(W-j for _,(j,_)in e[0])),(a==e[1]*i+e[2]for i,a in E(s,1))][[0]==e[:1]],(i==e[-1]for i in s)][[0,0]==e[:2]]):return i
 
print(F([1, 1, 1, 1, 1]))
print(F([1, 2, 3, 4, 5]))
print(F([3, 5, 7, 9, 11]))
print(F([1, 2, 4, 8, 16]))
print(F([1, 4, 7, 10, 13]))
print(F([1, 3, 6, 10]))
print(F([1, 2, 3, 5, 8]))
print(F([1, 8, 127, 2024, 32257, 514088, 8193151]))
print(F([7, 17, 27, 37, 47, 57, 67]))
print(F([1, 17, 289, 4913, 83521, 1419857]))
print(F([1, 1, 4, 10, 28, 76, 208, 568, 1552, 4240]))

ZnJvbSBtYXRoIGltcG9ydCoKSD1hYnMKRT1lbnVtZXJhdGUKZGVmIEMocyxjPVtdKToKIGlmW109PXMgYW5kIGM6eWllbGQgYztyZXR1cm4KIGlmIHM6eWllbGQgZnJvbVsqQyhzWzE6XSxjK1tzWzBdXSksKkMoc1sxOl0sYyldCkk9bGFtYmRhIFYsaTp7KDAsViksKFYvL2ksViVpKX0KZGVmIFcoeCx5KToKIHQ9W1t4LDEsMF0sW3ksMCwxXV0KIHdoaWxlIHRbLTFdWzBdOnE9dFstMl1bMF0vL3RbLTFdWzBdO3QrPVt0Wy0yXVswXSV0Wy0xXVswXSx0Wy0yXVsxXS1xKnRbLTFdWzFdLHRbLTJdWzJdLXEqdFstMV1bMl1dLAogcmV0dXJuIHRbLTJdCmRlZiBEKGEsYix4LHksZyk6CiBxPVsoMCwxLHgseSksKDAsLTEseCx5KV0KIHdoaWxlIHE6CiAgbSxkLFgsWT1xLnBvcCgwKTttKz1kCiAgaWYgYWxsKFtYLFldKTp5aWVsZChYLFkpCiAgSixLPXgrbSooYi9nKSx5LW0qKGEvZyk7cSs9WyhtLGQsSixLKV0qKEgoWCkrSChZKT5IKEopK0goSylvciAxPmFsbChbWCxZXSkpCmRlZiBmKHMpOgogZm9yIE8gaW4gcmFuZ2UoMSxsZW4ocykpOgogIGZvciBKIGluIHNvcnRlZChDKFsqRShzKV1bOk9dWzo6LTFdKSxrZXk9bGVuKToKICAgaWZ+LWxlbihKKToKICAgIHE9WyhKWzBdWzFdLFsoMSxKWzBdKV0sSlsxOl0sc1tPXSldCiAgICB3aGlsZSBxOgogICAgIHgsUixTLHY9cS5wb3AoMCkKICAgICBpZiBTOgogICAgICB5PVNbMF1bMV0KICAgICAgZm9yIGkgaW4gcmFuZ2Uodi0xKToKICAgICAgIGlmKHYtaSklZ2NkKHgseSk8MTpnLGEsYj1XKFg6PW1heCh4LHkpLFk6PW1pbih4LHkpKTtHPSh2LWkpLy9nO0EsQj1taW4oRChYLFksW2IsYV1beD55XSpHLFthLGJdW3g+eV0qRyxnKSxrZXk9bGFtYmRhIHg6c3VtKG1hcChILHgpKSk7cSs9KHYtaSxbKEEqeixsKWZvciB6LGwgaW4gUl0rWyhCLFNbMF0pXSxTWzE6XSxpKSwKICAgICBlbHNlOgogICAgICBmb3IgdSBpbiBJKHYsTysxKTp5aWVsZChbUiwqdV0sTykKICAgZWxzZToKICAgIHlpZWxkKFswLHNbT10vLy1+TyxzW09dJS1+T10sTykKICAgIGZvciB1IGluIEkoc1tPXSVKWzBdWzFdLE8rMSk6aj1zW09dLy9KWzBdWzFdO3lpZWxkKFtbKDEsSlswXSlmb3IgXyBpbiByYW5nZShqKV0sKnVdLE8pO3lpZWxkKFtbKGosSlswXSldLCp1XSxPKQpkZWYgRihzKToKIGZvciBpIGluIGYocyk6CiAgZSxXPWkKICBpZiBhbGwoW1soYT09c3VtKE4qc1tpK35XK0ldZm9yIE4sKEksXylpbiBlWzBdKStpKmVbMV0rZVsyXWZvciBpLGEgaW4gRShzLDEpaWYgaT5tYXgoVy1qIGZvciBfLChqLF8paW4gZVswXSkpLChhPT1lWzFdKmkrZVsyXWZvciBpLGEgaW4gRShzLDEpKV1bWzBdPT1lWzoxXV0sKGk9PWVbLTFdZm9yIGkgaW4gcyldW1swLDBdPT1lWzoyXV0pOnJldHVybiBpCiAgCnByaW50KEYoWzEsIDEsIDEsIDEsIDFdKSkKcHJpbnQoRihbMSwgMiwgMywgNCwgNV0pKQpwcmludChGKFszLCA1LCA3LCA5LCAxMV0pKQpwcmludChGKFsxLCAyLCA0LCA4LCAxNl0pKQpwcmludChGKFsxLCA0LCA3LCAxMCwgMTNdKSkKcHJpbnQoRihbMSwgMywgNiwgMTBdKSkKcHJpbnQoRihbMSwgMiwgMywgNSwgOF0pKQpwcmludChGKFsxLCA4LCAxMjcsIDIwMjQsIDMyMjU3LCA1MTQwODgsIDgxOTMxNTFdKSkKcHJpbnQoRihbNywgMTcsIDI3LCAzNywgNDcsIDU3LCA2N10pKQpwcmludChGKFsxLCAxNywgMjg5LCA0OTEzLCA4MzUyMSwgMTQxOTg1N10pKQpwcmludChGKFsxLCAxLCA0LCAxMCwgMjgsIDc2LCAyMDgsIDU2OCwgMTU1MiwgNDI0MF0pKQ==