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](https://en.wikipedia.org/wiki/Greatest_common_divisor).

What is the minimum number of operations you need to make all of the elements equal to 1?
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 *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — the elements of the array.
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.
5
2 2 3 4 6
5
4
2 4 6 8
-1
3
2 6 9
4
15
10 10 10 10 10 10 21 21 21 21 21 21 21 21 21
15
12
10 10 14 14 14 14 14 14 14 14 21 21
20
5
10 10 14 21 21
6
9
10 10 10 10 10 14 14 21 21
11
9
10 10 10 10 10 10 10 10 21
9
13
10 10 10 15 15 15 15 15 15 15 15 21 21
21
15
10 10 10 10 10 10 10 10 10 10 10 10 15 15 21
17
4
1 1 1 1
0
1
3
-1
2
1 1
0
2
1000000000 1000000000
-1
1
1000000000
-1
1
1
0
3
42 15 35
4
3
6 10 15
4
4
2 1 1 1
1
5
2 1 1 1 2
2
3
30 14 21
4
3
15 6 10
4
4
1 1 1 2
1
5
1 1 1 2 2
2
4
2 6 9 1
3
6
2 3 4 1 1 1
3
15
2 6 6 6 3 3 3 15 5 5 5 7 5 5 5
15
5
2 3 2 6 9
5
6
6 15 10 6 15 10
7
import sys,random,bisect
from collections import deque,defaultdict,Counter
from heapq import heapify,heappop,heappush
import math 
from types import GeneratorType
#from functools import cache  3.9
mod = 10**9+7
inf = int(1e20)
input = lambda: sys.stdin.readline().rstrip("\r\n")
MI = lambda :map(int,input().split())
li = lambda :list(MI())
ii = lambda :int(input())
py = lambda :print("YES")
pn = lambda :print("NO")




def gcd(n1,n2):
    return gcd(n2,n1%n2) if n2>0 else n1       #最大公约数


n=ii()

arr=li()

if 1 in arr:
    print(n-arr.count(1))
    exit()

g=arr[0]

for a in arr:
    g=gcd(g,a)

if g!=1:
    print(-1)
    exit()

st=[]
min_size=n
for i,a in enumerate(arr):
    for j in range(len(st)):
        st[j][0]=gcd(st[j][0],a)
    nst=[]
    for v,j in st:
        if len(nst)==0 or v!=nst[-1][0]:
            nst.append([v,j])
    nst.append([a,i])
    for j in range(len(nst)-1):
        v,s,e=nst[j][0],nst[j][1],nst[j+1][1]-1
    st=nst
    if st[0][0]==1:
        min_size=min(min_size,i-(st[1][1]-1)+1)
    #print(st)
    if len(st)>1 and st[-1][0]==st[-2][0]:
        st.pop()

print(min_size+n-2)

