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
sys.setrecursionlimit(100000000)
# def input(): return sys.stdin.readline()[:-1]
def iin(): return int(input())
def impin(): return map(int, input().split())
def irrin(): return [int(x) for x in input().split()]
def imrin(n): return [int(input()) for _ in range(n)]


# factorize number (maximum value = m**2)
def factorize(n, m):
    prr = []
    for i in range(2, m):
        cnt = 0
        while n%i==0 and n>1:
            n //= i
            cnt += 1
        if cnt:
            prr.append([i, cnt])
        if n==1:
            break
    if n!=1:
        prr.append([n, 1])
    return prr


# gcd
def gcd(x, y):
    if x<y:
        return gcd(y, x)
    while y>0:
        x, y = y, x%y
    return x


n = iin()
arr = irrin()
brr = arr[:]
for i in range(n):
    arr[i] = factorize(arr[i], 10**5)
c = 0
# print(arr)
# while True:
    # mn = 100000
    # mi = -1
    # for i in range(n):
    #     print(arr[i])
    #     if mn > len(arr[i]):
    #         mn = len(arr[i])
    #         mi = i
    # for x in arr[mi]:
    #     for i in range(n):
    #         have = False
    #         for y in arr[i]:
    #             if x[0]==y[0]:
    #                 have = True
    #                 break
    #         if not have:
    #             break
    #     else:
    #         print(-1)
    #         exit()

crr = []
for i in range(1, n):
    g = gcd(brr[i-1], brr[i])
    crr.append(g)
    if g==1:
        print(c+n)
        exit()
    # print(brr[i-1], g, brr[i])
mn = 1000000
for i in range(n-2):
    for j in range(i+1, n-1):
        if gcd(crr[i], crr[j])==1:
            mn = min(mn, j-i)
if mn==1000000:
    print(-1)
else:
    print(n+mn)
# break
