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?

Input

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 a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array.

Output

Print -1, if it is impossible to turn all numbers to 1. Otherwise, print the minimum number of operations needed to make all numbers equal to 1.

Examples

Input

5
2 2 3 4 6


Output

5


Input

4
2 4 6 8


Output

-1


Input

3
2 6 9


Output

4

Note

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.
import math

def nextfront(i, N, T):
	div = T[i]
	for j in range(i + 1, N):
		div = math.gcd(div, T[j])
		if div == 1:
			return j
	return -1


def nextback(k, N, T):
	div = T[k]
	for j in range(k - 1, -1):
		div = math.gcd(div, T[j])
		if div == 1:
			return j
	return -1


def qtduns(T, N):
	resp = 0
	for i in range(N):
		if T[i] == 1:
			resp+=1
	return resp


def main():
	N = int(input())
	T = [int(i) for i in input().split()]
	x = qtduns(T, N)
	if x > 0:
		print(N - x)
		return
	l = N + 1
	i = 0
	k = N + 1
	flag = False
	while i != N and l != 2:
		#print(i, k, l)
		div = T[i]
		for j in range(i + 1, N):
			div = math.gcd(div, T[j])
			if div == 1:
				l = min(l, j - i + 1)
				k = j
				#print(" ", i, j, l)
				break
		if div != 1:
			flag = True
			k = N - 1
		div = T[k]
		for j in range(k - 1, i - 1):
			div = math.gcd(div, T[j])
			if div == 1:
				l = min(l, k - j + 1)
				#print("  ", j, k, l)
				break
		if flag:
			break
		else:
			i = k - l + 2
	if l == N + 1:
		print(-1)
	else:
		print(N + l - 2)


main()

# 1511548364391
