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

cache = {}

def getMn(n):
    try:
        return cache[n]
    except:
        cache[n] = [1,n]
        i = 2
        while i<=n**0.5:
            if n%i==0:
                cache[n].append(i)
                cache[n].append(n//i)
            i+=1
        cache[n].sort()
        return cache[n]

def gcd(x,y):
    mnX = getMn(x)
    mnY = getMn(y)
    for i in range(len(mnX)-1,-1,-1):
        if mnX[i] in mnY:
            return mnX[i]

def getSteps(left,mid,right):
    steps = 0
    #print(left,mid,right)
    if left == 0:
        if gcd(mid,right)==1:
            steps = 1
    elif right == 0:
        if gcd(mid,left)==1:
            steps = 1
    else:
        steps1 = 0
        last = left
        leftStart = True
        tmpMid = mid
        while last!=mid:
            last = mid
            if leftStart:
                mid = gcd(left,mid)
            else:
                mid = gcd(right,mid)
            leftStart = not leftStart
            steps1+=1
            #print(mid)
        steps1-=1
        if mid == 1:
            steps = steps1

        mid = tmpMid
        steps2 = 0
        last = right
        leftStart = False
        while last!=mid:
            last = mid
            if leftStart:
                mid = gcd(left,mid)
            else:
                mid = gcd(right,mid)
            leftStart = not leftStart
            steps2+=1
        steps2-=1
        if mid == 1:
            if steps2<steps:
                steps = steps2
    #print(steps)
    return steps

ans = -1
n = int(sys.stdin.readline())
inp = str(sys.stdin.readline())[:-1].split()
nums = [int(x) for x in inp]

if n == 1 and nums[0]==1:
    ans = 0
else:
    c = nums.count(1)
    ans = n-c
    mnStart = 1000000000
    mn = mnStart
    if c == 0:
        for i in range(n):
            left = 0
            right = 0
            if i>0:
                left = nums[i-1]
            if i <n-1:
                right = nums[i+1]
            tmp = getSteps(left,nums[i],right)
            if tmp!=0:
                if tmp<mn:
                    mn = tmp
        if mn == mnStart:
            ans = -1
        else:
            ans += (mn-1)
print(ans)
        
