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
# coding=utf-8
from math import gcd,inf
 
m = 0
def build(k,l,r):
    global m
    if l == r:
        tree[k] = a[l]
        if tree[k] == 1:
            m += 1  # ç¬¬ä¸ç§æåµ
        return
    mid = l + r >> 1
    build(k << 1,l,mid)
    build(k << 1 | 1,mid + 1,r)
    tree[k] = gcd(tree[k << 1],tree[k << 1 | 1])
 
def queryGCD(k,l,r,x,y):
    if l == x and r == y: return tree[k]
    mid = l + r >> 1
    if y <= mid:     g = queryGCD(k << 1,l, mid,x,y)
    else:
        if x > mid:  g = queryGCD(k << 1 | 1,mid + 1, r ,x,y)
        else:        g = gcd( queryGCD(k << 1,l, mid,x,mid) ,queryGCD(k << 1|1,mid + 1, r,mid + 1,y) )
    return g
 
def main():
    global tree,a,m
    n = int(input())
    a = [0] + list(map(int,input().split()))
    tree = [0] * (4 * n)
    build(1,1,n)  # å»ºæ 
    if m > 0:   print(n - m)
    else:
        m,i = inf,1
        for j in range(1,n+1):
            while i < j and queryGCD(1,1,n,i + 1,j) == 1:   i += 1
            if queryGCD(1,1,n,i,j) == 1:                    m = min(j - i,m)
 
        print(n + m - 1 if m < n else -1 )
 
main()
		      				     		 	 	 		 	 		