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
from math import gcd
class Node:
  def __init__(self,l,r):
    self.l,self.r = l,r
    self.left = self.right = None
    self.val = 0
class segtree:
  def __init__(self,a):
    self.a = a
    self.rt = Node(0,len(a)-1)
    self.build(self.rt)
  def build(self,node):
    if node.l == node.r:
      node.val = self.a[node.l]
      return 
    mid = node.l+node.r>>1
    node.left,node.right = Node(node.l,mid),Node(mid+1,node.r)
    self.build(node.left);self.build(node.right)
    node.val = gcd(node.left.val,node.right.val)
  def find(self,node,low,hig):
    if low == node.l and hig == node.r:
      return node.val
    mid = node.l+node.r>>1
    res = []
    if low <= mid:
      res.append(self.find(node.left,low,min(hig,mid)))
    if hig >= mid+1:
      res.append(self.find(node.right,max(low,mid+1),hig))
    if len(res) == 2:return gcd(res[0],res[1])
    return res[0]
n = int(input())
a = list(map(int,input().split()))
seg = segtree(a)
if 1 in a:
  print(n-a.count(1))
else:
  ans = n+1
  for i in range(n):
    l,r = i,n
    while l+1 != r:
      mid = l+r>>1
      if seg.find(seg.rt,i,mid) != 1:
        l = mid
      else:
        r = mid
    if r != n:ans = min(ans,(l-i+1))
  if ans == n+1:print(-1)
  else:print(ans+n-1)
