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 io
import os
import sys
from collections import deque
from functools import reduce, lru_cache
from math import gcd, inf

if sys.hexversion == 50923504:
    sys.stdin = open('input.txt')
else:
    input = sys.stdin.buffer.readline
MOD = 10 ** 9 + 7


class IntervalTree:
    def __init__(self, size, nums=None):
        self.size = size
        self.nums = nums
        self.interval_tree = [0] * (size * 4)
        if nums:
            self.build_tree(1, 1, size)

    def build_tree(self, p, l, r):
        interval_tree = self.interval_tree
        nums = self.nums
        if l == r:
            interval_tree[p] = nums[l - 1]
            return
        mid = (l + r) // 2
        self.build_tree(p * 2, l, mid)
        self.build_tree(p * 2 + 1, mid + 1, r)
        interval_tree[p] = gcd(interval_tree[p * 2], interval_tree[p * 2 + 1])

    @lru_cache()
    def gcd_interval(self, p, l, r, x, y):
        if y < l or r < x:
            return 1
        interval_tree = self.interval_tree
        if x <= l and r <= y:
            return interval_tree[p]
        mid = (l + r) // 2
        a = b = None
        if x <= mid:
            a = self.gcd_interval(p * 2, l, mid, x, y)
        if mid < y:
            b = self.gcd_interval(p * 2 + 1, mid + 1, r, x, y)
        if not a:
            return b
        if not b:
            return a
        return gcd(a, b)


def my_bisect_left(a, x, lo=None, hi=None, key=None):
    """
    由于3.10才能用key参数，因此自己实现一个。
    :param a: 需要二分的数据
    :param x: 查找的值
    :param lo: 左边界
    :param hi: 右边界(闭区间)
    :param key: 数组a中的值会依次执行key方法，
    :return: 第一个大于等于x的下标位置
    """
    if not lo:
        lo = 0
    if not hi:
        hi = len(a) - 1
    else:
        hi = min(hi, len(a) - 1)
    size = hi - lo + 1

    if not key:
        key = lambda _x: _x
    while size:
        half = size >> 1
        mid = lo + half
        if key(a[mid]) < x:
            lo = mid + 1
            size = size - half - 1
        else:
            size = half
    return lo


def solve(n, a):
    if reduce(gcd, a) != 1:
        return print(-1)
    c = a.count(1)
    if c:
        return print(n - c)
    tree = IntervalTree(n, a)
    ans = inf

    for i in range(1, n):
        def query(k):
            return -tree.gcd_interval(1, 1, n, i, k)

        hi = min(i + ans, n - 1)
        pos = my_bisect_left(range(n+1), -1, lo=i + 1,  key=query)
        ans = min(ans, pos - i )

    print(ans + n - 1)


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    solve(n, a)
