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 __future__ import print_function # for PyPy2
from collections import Counter, OrderedDict
from itertools import permutations as perm
from fractions import Fraction
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
from math import *

g   = lambda : stdin.readline().strip()
gl  = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1e9)+7
inf = float("inf")                      

n, = gil()
a = gil()

if a.count(1):
	print(n-a.count(1))
	exit()


seg = inf
for l in range(n-1):
	x = gcd(a[l], a[l+1])
	r = l+1
	# print(x, a[l], a[l+1])
	while x != 1 and r+1 < n:
		r += 1
		# print(gcd(x, a[r]), x, a[r], "*")
		x = gcd(x, a[r])

	if x == 1 and r-l < seg :
		seg = r-l

print(seg+n-1)
