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.

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 a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — 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.

Source: codeforces | Difficulty: MEDIUM
Tags: Greedy algorithms

Complete search

Number theory

Dynamic programming

Mathematics


Solutions:
import math
n = int(input())
l = list(map(int, input().split()))
count = 0
for i in range(n):
	if l[i] == 1:
		count += 1
if count != 0:
	print(n - count)
	exit()
ss = 0
mi = 10 ** 9 + 7
for i in range(n):
	ss = l[i]
	for j in range(i + 1, n):
		ss = math.gcd(l[j], ss)
		if ss == 1:
			mi = min(mi, j - i)
if mi == 10 ** 9 + 7:
	print(-1)
else:
	print(mi + n - 1)


from math import gcd
n = int(input())
j = [int(x) for x in input().split(' ')]

def screen(l):
	o = []
	for i in range(len(l) - 1):
		c = gcd(l[i], l[i + 1])
		if c == 1:
			return 1
		else:
			o.append(c)
	return o
if n == 1:
	if j[0] == 1:
		print(0)
	else:
		print(-1)
else:
	d = j.count(1)
	if d == 0:
		t = j
		for i in range(len(j) - 1):
			r = screen(t)
			if r == 1:
				print(i + n)
				break
			else:
				t = r
		if t != 1:
			if len(t) == 1:
				print(-1)
	else:
		print(n - d)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
n1 = a.count(1)
if n1:
	print(n - n1)
	exit()
ret = float('inf')
for left in range(n):
	g = a[left]
	for right in range(left, n):
		g = gcd(g, a[right])
		if g == 1:
			ret = min(ret, n + right - left - 1)
print(ret if ret != float('inf') else -1)


import sys
from math import gcd
n = int(input())
a = list(map(int, input().split()))
if 1 in a:
	print(n - a.count(1))
	exit()
count = sys.maxsize
for i in range(n):
	tmp = a[i]
	for j in range(i + 1, n):
		tmp = gcd(tmp, a[j])
		if tmp == 1:
			count = min(count, n + j - i - 1)
if count != sys.maxsize:
	print(count)
else:
	print(-1)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial
from collections import deque

def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	while a % b != 0:
		(a, b) = (b, a % b)
	return b
n = int(input())
l = list(map(int, input().split()))
t = l.count(1)
if t >= 1:
	print(n - t)
	exit()
else:
	z = list(l)
	a = 1
	while len(z) > 1:
		for i in range(len(z) - 1):
			z[i] = gcd(z[i], l[i + a])
			if z[i] == 1:
				print(n - 1 + a)
				exit()
		z.pop()
		a += 1
print(-1)


import itertools
import bisect
import math
from collections import *
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def main():
	n = ii()
	a = lmii()
	gg = a[0]
	cnt = a.count(1)
	for i in range(n):
		gg = math.gcd(gg, a[i])
	if gg != 1:
		print(-1)
	elif cnt:
		print(n - cnt)
	else:
		cnt = 0
		ans = sys.maxsize
		for i in range(n):
			val = a[i]
			for j in range(i, n):
				val = math.gcd(val, a[j])
				if val == 1:
					pp = j - i
					ans = min(ans, pp)
		print(ans + (n - 1))
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def nod(x, y):
	if x % y == 0:
		return y
	else:
		return nod(y, x % y)
n = int(input())
a = list(map(int, input().split()))
k = 0
for i in a:
	if i == 1:
		k += 1
if k > 0:
	print(n - k)
else:
	md = n + 1
	for i in range(0, n - 1):
		d = a[i]
		for j in range(i + 1, n):
			x = max(d, a[j])
			y = min(d, a[j])
			d = nod(x, y)
			if d == 1 and md > j - i + 1:
				md = j - i + 1
				break
	print(n + md - 2 if md < n + 1 else -1)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	if gcd_of_array(a) != 1:
		print(-1)
	elif a.count(1) == 0:
		left = 2
		right = n
		best = n
		while left <= right:
			mid = (left + right) // 2
			if check(a, mid):
				right = mid - 1
				best = min(mid, best)
			else:
				left = mid + 1
		ans = n + best - 2
		print(ans)
	else:
		print(n - a.count(1))

def check(a, le):
	for i in range(len(a) - le + 1):
		if gcd_of_array(a[i:i + le]) == 1:
			return True
	return False

def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)

def gcd_of_array(a):
	res = a[0]
	for i in a:
		res = gcd(res, i)
		if res == 1:
			break
	return res
main()


from math import gcd
n = int(input())
l = [int(i) for i in input().split(' ')]
x = l.count(1)
result = 10000000000.0 + 5
if x > 0:
	print(n - x)
	exit(0)
for L in range(n - 1):
	temp = l[L]
	for R in range(L + 1, n):
		temp = gcd(temp, l[R])
		if temp == 1:
			r = R - L
			result = min(result, r)
if result == 10000000000.0 + 5:
	print(-1)
else:
	print(n + result - 1)


from math import gcd
n = int(input())
l = list(map(int, input().split()))
if l.count(1) > 0:
	print(n - l.count(1))
	exit()
m = 10 ** 12
i = 0
while i < n:
	j = i + 1
	x = l[i]
	while j < n:
		if gcd(x, l[j]) == 1:
			d = abs(j - i)
			if d < m:
				m = d
		x = gcd(x, l[j])
		j += 1
	i += 1
if m == 10 ** 12:
	print(-1)
	exit()
else:
	print(m + (n - 1))


def gcd(a: int, b: int):
	return gcd(b, a % b) if b else a
nb = int(input())
s = input()
numbers = [int(i) for i in s.split(' ')]
number = -1
flag = True
op = 0

def count1(s):
	res = 0
	for i in s:
		if i == 1:
			res += 1
	return res
if nb == 1:
	if numbers[0] == 1:
		print(0)
	else:
		print(-1)
else:
	while op < 2010:
		new = []
		for i in range(0, len(numbers) - 1):
			g = gcd(numbers[i], numbers[i + 1])
			if g == 1:
				number = nb + op - count1(numbers)
				numbers = []
				print(number)
				return
			else:
				new.append(g)
		numbers = new
		op += 1
	print(number)


import math
n = int(input())
a = list(map(int, input().split()))
x = [1 for x in a if x == 1]
x = len(x)
if x >= 1:
	print(n - x)
	quit()
ans = n
for i in range(n):
	g = a[i]
	for j in range(i, n):
		g = math.gcd(g, a[j])
		if g == 1:
			ans = min(ans, j - i)
if ans == n:
	print(-1)
else:
	print(ans + n - 1)


from math import gcd
from functools import *

@lru_cache(maxsize=None)
def gcd1(a, b):
	return gcd(a, b)

def solve(k, n, a, g):
	for i in range(n - k):
		g[i] = gcd1(g[i], a[i + k])
		if g[i] == 1:
			return k
	return -1

def easy():
	n = int(input())
	a = [int(i) for i in input().split()]
	g = a[:]
	if n == 1:
		if a[0] == 1:
			print(0)
		else:
			print(-1)
	elif a.count(1) != 0:
		print(n - a.count(1))
	else:
		for i in range(n):
			cur = solve(i, n, a, g)
			if cur == i:
				print(n + cur - 1)
				break
		else:
			print(-1)
easy()


import math
n = int(input())
list_ = list(map(int, input().split()))
if 1 in list_:
	print(n - list_.count(1))
else:
	result = n + 1
	for i in range(n):
		cnt = 0
		gcd = list_[i]
		for j in range(n - i):
			gcd = math.gcd(gcd, list_[i + j])
			if gcd == 1:
				result = min(result, cnt)
			cnt += 1
	if result == n + 1:
		print(-1)
	else:
		print(result + n - 1)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
lst = list()
lst = input().split(' ')
num = 0
flag = 0
for i in lst:
	if int(i) == 1:
		num += 1
if num != 0:
	print(n - num)
	exit()
for i in range(1, n):
	for j in range(n - i):
		lst[j] = gcd(int(lst[j]), int(lst[j + 1]))
		if int(lst[j]) == 1:
			print(i + n - 1)
			flag = 1
			break
	if flag != 0:
		break
if not flag:
	print(-1)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def gcda(a):
	ans = a[0]
	for i in range(1, len(a)):
		ans = gcd(a[i], ans)
	return ans
n = int(input())
a = list(map(int, input().split()))
if 1 in a:
	print(sum([1 for i in a if i != 1]))
	return
if gcda(a) != 1:
	print(-1)
	return
mr = n + 1
for i in range(n):
	g = a[i]
	for j in range(i + 1, n):
		g = gcd(g, a[j])
		if g == 1:
			mr = min(mr, j - i)
			break
print(mr + n - 1)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
memo = {}

def is_prime(n):
	if n < 1:
		return False
	if n == 1:
		return True
	if n in memo:
		return memo[n]
	i = 2
	while i * i <= n:
		if n % i == 0:
			memo[n] = False
			return False
		i += 1
	memo[n] = True
	return True
n = int(input())
a = list(map(int, input().split()))
tot = 0
for i in range(n):
	if a[i] == 1:
		tot += 1
if tot > 0:
	print(n - tot)
	exit(0)
tot = 0
best = 10 ** 9
for i in range(n):
	cur = a[i]
	for j in range(i + 1, n):
		cur = gcd(cur, a[j])
		if cur == 1:
			best = min(best, j - i)
if best == 10 ** 9:
	print('-1')
else:
	print(n + best - 1)


import sys
import collections
from collections import Counter, deque
import itertools
import math
import timeit
import random

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	divisors = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				divisors.append(i)
			else:
				divisors.extend([i, n // i])
	return divisors

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def flin(d, x, default=-1):
	left = right = -1
	for i in range(len(d)):
		if d[i] == x:
			if left == -1:
				left = i
			right = i
	if left == -1:
		return (default, default)
	else:
		return (left, right)

def ceil(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)
n = ii()
d = li()
_d = [x for x in d if x != 1]
if len(d) != len(_d):
	exit(print(len(_d)))
gcds = []
for i in range(n - 1):
	t = math.gcd(d[i], d[i + 1])
	if t == 1:
		exit(print(n))
	gcds.append(t)
r = 10 ** 6
for i in range(n - 1):
	for j in range(i + 2, n):
		if math.gcd(gcds[i], d[j]) == 1:
			r = min(r, j - i - 1 + n)
print(r) if r != 10 ** 6 else print(-1)


import math
n = int(input())
arr = [int(x) for x in input().split()]
k = arr.count(1)
if k != 0:
	print(n - k)
else:
	min = float('inf')
	for i in range(n - 1):
		g = arr[i]
		for j in range(i + 1, n):
			g = math.gcd(g, arr[j])
			if g == 1:
				if j - i < min:
					min = j - i
				break
	if min < float('inf'):
		print(min + n - 1)
	else:
		print('-1')


from collections import Counter
import math
n = int(input())
arr = list(map(int, input().split()))
counter = Counter(arr)
if counter[1] > 0:
	print(n - counter[1])
	exit(0)

def find_result(arr):
	counter = 1
	while len(arr) > 1:
		newarr = []
		for i in range(len(arr) - 1):
			hcf = math.gcd(arr[i], arr[i + 1])
			if hcf == 1:
				return counter
			newarr.append(hcf)
		counter += 1
		arr = newarr
	return -1 if arr[0] != 1 else counter
rounds_to_achieve_1 = find_result(arr)
if rounds_to_achieve_1 == -1:
	print(-1)
else:
	print(len(arr) - 1 + rounds_to_achieve_1)


from fractions import gcd
n = int(input())
a = [int(z) for z in input().split()]
cnt = 0
for i in range(n):
	if a[i] == 1:
		cnt += 1
if cnt > 0:
	print(n - cnt)
	return
minlen = 1000000000
for l in range(n):
	cur = a[l]
	for r in range(l + 1, n):
		cur = gcd(cur, a[r])
		if cur == 1:
			minlen = min(minlen, r - l)
if minlen == 1000000000:
	print(-1)
else:
	print(minlen + n - 1)


import math
n = int(input())
a = list(map(int, input().split()))
cnt_one = 0
for i in range(n):
	if a[i] == 1:
		cnt_one += 1
if cnt_one > 0:
	print(n - cnt_one)
	quit()
L = n + 1
for i in range(n):
	cur = a[i]
	for j in range(i, n):
		cur = math.gcd(cur, a[j])
		if cur == 1:
			L = min(L, j - i + 1)
			break
if L == n + 1:
	print(-1)
else:
	print(L + n - 2)


n = int(input())
A = list(map(int, input().split()))
if n == 1:
	if A[0] != 1:
		print(-1)
	else:
		print(0)
	exit()
import math
from functools import reduce

def gcd(*numbers):
	return reduce(math.gcd, numbers)

def gcd_list(numbers):
	return reduce(math.gcd, numbers)
g = gcd_list(A)
if g != 1:
	print(-1)
	exit()
cnt = 0
for i in range(n):
	if A[i] == 1:
		cnt += 1
if cnt:
	print(n - cnt)
	exit()
while len(A) >= 2:
	B = []
	for i in range(len(A) - 1):
		B.append(gcd(A[i], A[i + 1]))
	for i in range(len(B)):
		if B[i] == 1:
			print(n - len(B) + n - 1)
			exit()
	A = B


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
nums = int(input())
array = input().split()
flag = False
cnt = 0
for obj in array:
	if int(obj) == 1:
		flag = True
	else:
		cnt += 1
if cnt != len(array):
	print(cnt)
else:
	minn_time = 2147483647
	for i in range(0, len(array)):
		if i != len(array) - 1:
			p = int(array[i + 1])
		else:
			p = int(array[i])
		for j in range(i + 1, len(array)):
			if j == i + 1:
				p = gcd(p, int(array[i]))
			else:
				p = gcd(p, int(array[j]))
			if p == 1:
				minn_time = min(minn_time, j - i)
				flag = True
	if minn_time == 2147483647:
		print('-1')
	else:
		print(minn_time + cnt - 1)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
l = list(map(int, input().split()))
c = 0
f = 0
if 1 in l:
	print(n - l.count(1))
else:
	while True:
		c += 1
		for i in range(n - c):
			a = gcd(l[i], l[i + 1])
			if a == 1:
				f = 1
				break
			l[i] = a
		if f == 1:
			break
		if c == n:
			break
	if f == 0:
		print(-1)
	else:
		print(c + n - 1)


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b > 0:
		r = a % b
		(a, b) = (b, r)
	return a

def solve():
	n = int(input())
	al = [int(i) for i in input().split()]
	if 1 in al:
		print(n - al.count(1))
		return
	ans = -1
	for i in range(n):
		t = al[i]
		for j in range(i + 1, n):
			t = gcd(t, al[j])
			if t == 1:
				if ans == -1:
					ans = j - i + (n - 1)
				else:
					ans = min(ans, j - i + (n - 1))
	print(ans)
solve()


import math

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: math.gcd(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
n = int(input())
l = list(map(int, input().split()))
if 1 in l:
	print(n - l.count(1))
else:
	s = SegmentTree(l)
	m = 999999999999999999999999
	for i in range(n):
		for j in range(i, n):
			if s.query(i, j) == 1:
				m = min(m, j - i + 1)
	if m == 999999999999999999999999:
		print(-1)
	else:
		print(n - 2 + m)


def gcd(a, b):
	while b:
		a %= b
		(a, b) = (b, a)
	return a
n = int(input())
l = list(map(int, input().split()))
g = l[0]
for i in range(1, n):
	g = gcd(g, l[i])
if g != 1:
	print(-1)
else:
	a = l.count(1)
	if a > 0:
		print(n - a)
	else:
		ans = float('inf')
		for i in range(n):
			g = l[i]
			for j in range(i + 1, n):
				g = gcd(g, l[j])
				if g == 1:
					d = j - i + n - 1
					ans = min(ans, d)
		print(ans)


from queue import PriorityQueue
from queue import Queue
import math
from collections import defaultdict
import sys
import operator as op
from functools import reduce
n = int(input())
ar = list(map(int, input().split()))
if ar.count(1) > 0:
	print(n - ar.count(1))
else:
	mi = n + 1
	for k in range(n):
		it = k + 1
		g = ar[k]
		while it < n:
			g = math.gcd(g, ar[it])
			if g == 1:
				mi = min(mi, it - k)
				break
			it += 1
	if mi == n + 1:
		print(-1)
	else:
		print(mi + n - 1)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
N = int(input())
A = [int(x) for x in input().split()]

def gcd(x, y):
	if x < y:
		(x, y) = (y, x)
	if y == 0:
		return x
	return gcd(x % y, y)
if any([v == 1 for v in A]):
	print(len([v for v in A if v != 1]))
else:
	d = float('inf')
	for i in range(N):
		v = A[i]
		for j in range(i + 1, min(N, i + d + 1)):
			v = gcd(v, A[j])
			if v == 1:
				d = min(d, j - i)
	if d != float('inf'):
		print(d + N - 1)
	else:
		print(-1)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
ans = -1
ones = a.count(1)
g = a[0]
for x in a:
	g = gcd(g, x)
if ones > 0:
	ans = n - ones
elif g == 1:
	ans = n + n - 1
	for i in range(n):
		g = a[i]
		sz = 1
		while i + 1 < n and g > 1:
			sz += 1
			i += 1
			g = gcd(g, a[i])
		if g == 1:
			ans = min(ans, sz - 1 + n - 1)
print(ans)


from math import gcd
n = int(input())
arr = list(map(int, input().split()))
ones = arr.count(1)
if ones > 0:
	print(n - ones)
else:
	gcds = [[0] * n for i in range(n)]
	for i in range(n):
		gcds[i][i] = arr[i]
	seglen = 10000
	for i in range(n + 1):
		for j in range(i + 1, n):
			gcds[i][j] = gcd(gcds[i][j - 1], arr[j])
			if gcds[i][j] == 1:
				seglen = min(seglen, j - i + 1)
	if seglen == 10000:
		print(-1)
	else:
		makeone = seglen - 1
		ones = 1
		res = makeone + n - ones
		print(res)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
N = int(input())
a = [int(x) for x in input().split()]
count1 = 0
for i in range(N):
	if a[i] == 1:
		count1 += 1
if count1 > 0:
	print(N - count1)
	exit()
minimum = N + 1
for i in range(N):
	L = gcd(0, a[i])
	for j in range(N - i):
		L = gcd(L, a[i + j])
		if L == 1:
			minimum = min(minimum, j)
if minimum != N + 1:
	print(N + minimum - 1)
else:
	print('-1')


from math import gcd

def main():
	n = int(input())
	a = b = list(map(int, input().split()))
	if 1 in b:
		print(n - b.count(1))
		return
	while b:
		b = [gcd(*p) for p in zip(a, b[1:])]
		if 1 in b:
			print(n * 2 - len(b) - 1)
			return
	print(-1)
main()


def gcd(a, b):
	return b if a == 0 else gcd(b % a, a)

def fun():
	if r:
		return n - r
	for i in range(1, n):
		for j in range(n):
			if j + i >= n:
				break
			a[j] = gcd(a[j], a[j + 1])
			if a[j] == 1:
				return i + n - 1
	return -1
n = int(input())
a = list(map(int, input().split()))
r = 0
for i in range(n):
	if a[i] == 1:
		r += 1
print(fun())


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
size = inp()
arr = inlt()
i = 0
count = size - arr.count(1)
arr1 = []
while i < size - 1:
	j = math.gcd(arr[i], arr[i + 1])
	arr1.append(j)
	if j == 1:
		i += 33 * size
	else:
		i += 1
	if i == size - 1:
		count += 1
		arr = arr1
		arr1 = []
		i = 0
		size -= 1
if len(arr) == 1 and arr[0] > 1:
	print(-1)
else:
	print(count)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
g = a[0]
one = 0
ev = 0
odd = 0
for x in a:
	if x == 1:
		one += 1
	if x % 2 == 0:
		ev += 1
	else:
		odd += 1
if one > 0:
	print(n - one)
elif odd == n or ev == n:
	print(-1)
else:
	t = n + 2
	for i in range(n):
		g = a[i]
		x = 0
		for j in range(i + 1, n):
			x += 1
			g = gcd(g, a[j])
			if g == 1:
				t = min(t, x)
	print(n + t - 1)


import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = list(map(int, input().split()))
m = n + 1
ct = 0
for i in a:
	if i == 1:
		ct += 1
if ct > 0:
	print(n - ct)
else:
	for i in range(n):
		g = a[i]
		for j in range(i + 1, n):
			g = math.gcd(g, a[j])
			if g == 1:
				m = min(m, j - i)
				break
	if m == n + 1:
		m = -1
	else:
		m += n - 1
	print(m)


from functools import reduce

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
a = list(map(int, input().split(' ')))
if a.count(1) > 0:
	print(n - a.count(1))
	exit(0)
c = reduce(gcd, a)
if c != 1:
	print(-1)
	exit(0)
c = n
for i in range(0, n - 1):
	g = a[i]
	for j in range(i + 1, n):
		g = gcd(g, a[j])
		if g == 1:
			c = min(c, j - i)
			break
print(c + n - 1)


n = int(input())
l = list(map(int, input().split()))
cnt1 = l.count(1)
if 0 < cnt1:
	print(n - cnt1)
	return
import math
m = n + 1
for i in range(n):
	g = l[i]
	for j in range(n - i):
		g = math.gcd(g, l[i + j])
		if g == 1:
			m = min(m, j)
if m == n + 1:
	print(-1)
else:
	print(m + n - 1)


n = int(input(''))
s = list(map(int, input('').split()))
a = s.count(1)
ans = 0

def gcd(x, y):
	(x, y) = (max(x, y), min(x, y))
	if y == 0:
		return x
	return gcd(y, x % y)
if a != 0:
	ans = n - a
else:
	dp = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		dp[i][i] = s[i]
	mins = n
	for i in range(n):
		for j in range(i, n):
			dp[i][j] = gcd(dp[i][j - 1], s[j])
			if dp[i][j] == 1:
				mins = min(j - i, mins)
	if mins == n:
		ans = -1
	else:
		ans = mins + (n - 1)
print(ans)


def read():
	return list(map(int, input().split()))

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def check(l):
	for t in l:
		if t != 1:
			return False
	else:
		return True

def main():
	n = int(input())
	l = read()
	ones = len(list(filter(lambda i: i == 1, l)))
	if ones > 0:
		return n - ones
	sum = 10000000000.0
	for i in range(n - 1):
		g = 0
		for j in range(i, n):
			g = gcd(g, l[j])
			if g == 1:
				sum = min(sum, j - i + n - 1)
	return sum if sum != 10000000000.0 else -1
print(main())


import math
n = int(input())
a = list(map(int, input().split()))
c = 0
ans = n
for i in a:
	if i == 1:
		c += 1
if c >= 1:
	print(n - c)
	quit()
for i in range(n):
	t = a[i]
	for j in range(i, n):
		t = math.gcd(t, a[j])
		if t == 1:
			ans = min(ans, j - i)
if ans == n:
	print(-1)
else:
	print(ans + n - 1)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
n = int(input())
a = list(map(int, input().split()))
o = a.count(1)
if n == 1:
	if a[0] == 1:
		print(0)
	else:
		print(-1)
else:
	ans = 10 ** 9
	for i in range(n):
		g = a[i]
		for j in range(i + 1, n):
			g = gcd(a[j], g)
			if g == 1:
				ans = min(ans, n - 1 + j - i - o)
				break
	if ans == 10 ** 9:
		print(-1)
	else:
		print(ans)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(n):
	if a[i] == 1:
		cnt += 1
if cnt > 0:
	print(max(0, n - cnt))
	exit()
ans = 10 ** 18
for l in range(n):
	g = a[l]
	r = l + 1
	while r < n:
		g = gcd(g, a[r])
		if g == 1:
			break
		r += 1
	if g == 1:
		ans = min(ans, r - l + n - 1)
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
n = int(input())
a = [int(x) for x in input().split()]
ones = 0
for i in range(n):
	if a[i] == 1:
		ones += 1
mini = n + 1
if ones == 0:
	for i in range(n):
		g = a[i]
		for j in range(i, n):
			g = gcd(g, a[j])
			if g == 1:
				mini = min(mini, j - i)
else:
	mini = 0
	ones -= 1
if mini == n + 1:
	ans = -1
else:
	ans = mini + len(a) - 1 - ones
print(ans)


n = int(input())
array = list(map(int, input().split()))

def gcd(a, b):
	if b > 0:
		return gcd(b, a % b)
	else:
		return a
allGcd = array[0]
for elem in array:
	allGcd = gcd(allGcd, elem)
if allGcd > 1:
	print(-1)
else:
	ones = 0
	for elem in array:
		if elem == 1:
			ones += 1
	if ones > 1:
		print(n - ones)
	else:
		res = 2000000000
		for i in range(n):
			tmp = array[i]
			for j in range(i, n):
				tmp = gcd(tmp, array[j])
				if tmp == 1:
					res = min(res, j - i)
		print(n + res - 1)


import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict, Counter
inp = sys.stdin.readline
read = lambda : list(map(int, inp().strip().split()))

def solve():
	n = int(input())
	arr = read()
	one_count = arr.count(1)
	if one_count:
		print(n - one_count)
		return
	ans = 10 ** 5
	flag = 0
	for i in range(n):
		_gcd = arr[i]
		for j in range(i + 1, n):
			_gcd = gcd(_gcd, arr[j])
			if _gcd == 1:
				flag = 1
				ans = min(ans, j - i + n - 1)
				break
	print([-1, ans][flag == 1])
solve()


import math
n = int(input())
l = list(map(int, input().split()))
mi = 100000000000000000000
for i in range(n):
	prev = l[i]
	if prev == 1:
		mi = 1
	for j in range(i + 1, n):
		prev = math.gcd(l[j], prev)
		if prev == 1:
			mi = min(mi, j - i)
if mi != 100000000000000000000:
	print(mi + n - l.count(1) - 1)
else:
	print(-1)


import math
n = int(input())
s = input()
a = list(map(int, s.split()))
cnt = 0
for i in a:
	if i == 1:
		cnt += 1
if cnt >= 1:
	print(n - cnt)
	quit()
ans = n
for i in range(n):
	tmp = a[i]
	for j in range(i, n):
		tmp = math.gcd(tmp, a[j])
		if tmp == 1:
			ans = min(ans, j - i)
if ans == n:
	print(-1)
else:
	print(ans + n - 1)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
(m, k, s) = (a[0], 0, a.count(1))
for i in range(1, n):
	m = gcd(m, a[i])
	k |= gcd(a[i], a[i - 1]) == 1
if m != 1:
	print(-1)
	exit()
if s:
	print(n - s)
elif k:
	print(n)
else:
	d = n
	for i in range(n):
		m = a[i]
		for j in range(i + 1, n):
			m = gcd(m, a[j])
			if m == 1:
				d = min(d, j - i - 1)
				break
	print(n + d)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
m = 100000000000.0
for i in range(n):
	g = None
	for j in range(i, n):
		if g is None:
			g = gcd(a[i], a[j])
		else:
			g = gcd(g, a[j])
		if g == 1:
			m = min(m, j - i)
if m == 100000000000.0:
	print(-1)
else:
	print(m + n - max(1, a.count(1)))


import math
n = int(input())
arr = list(map(int, input().split()))
cntof1 = 0
for i in arr:
	if i == 1:
		cntof1 += 1
if cntof1 >= 1:
	print(n - cntof1)
else:
	minimum = 10 ** 9
	for L in range(n):
		gc = arr[L]
		for R in range(L + 1, n):
			gc = math.gcd(gc, arr[R])
			if gc == 1:
				minimum = min(minimum, R - L)
				break
	if minimum == 10 ** 9:
		print(-1)
	else:
		print(minimum + n - 1)


import math
n = int(input())
arr = list(map(int, input().split()))
cnt_1 = arr.count(1)
if cnt_1 > 0:
	print(n - cnt_1)
else:
	minn = n
	for i in range(n):
		g = arr[i]
		for j in range(i, n):
			g = math.gcd(g, arr[j])
			if g == 1:
				minn = min(minn, j - i)
				break
	if minn == n:
		print(-1)
	else:
		print(minn + n - 1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import math
from math import inf
import bisect
n = int(input())
arr = list(map(int, input().split()))
if 1 in arr:
	print(n - arr.count(1))
else:
	ans = 20002
	for i in range(n):
		var = arr[i]
		for j in range(i + 1, n):
			var = math.gcd(var, arr[j])
			if var == 1:
				ans = min(j - i + 1, ans)
				break
	t = ans - 1 + n - 1
	print(t if t != 20002 - 1 + n - 1 else -1)


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
n = int(input())
a = list(map(int, input().split()))
if 1 in a:
	print(n - a.count(1))
else:
	mins = n
	k = False
	for l in range(n - 1):
		x = a[l]
		for r in range(l + 1, n):
			x = gcd(x, a[r])
			if x == 1:
				k = True
				mins = min(mins, r - l + 1)
	print(mins + n - 2 if k else -1)


from sys import setrecursionlimit
from collections import Counter
setrecursionlimit(1000000)
d = {}

def nod(a, b):
	if a == 0:
		return b
	if b == 0:
		return a
	if a == b:
		return a
	if a == 1 or b == 1:
		return 1
	if a % 2 == 0:
		if b % 2 == 0:
			return 2 * nod(a // 2, b // 2)
		else:
			return nod(a // 2, b)
	elif b % 2 == 0:
		return nod(b // 2, a)
	elif a > b:
		return nod(b, (a - b) // 2)
	else:
		return nod((b - a) // 2, a)

def nod2(a, b):
	try:
		return d[a, b]
	except:
		c = nod2(a, b)
		d[a, b] = c
		return c
n = int(input())
a = list(map(int, input().split()))
z = a[0]
for i in a:
	z = nod(z, i)
if z != 1:
	print(-1)
else:
	z = 0
	if 1 in a:
		print(n - Counter(a)[1])
		exit()
	else:
		while not 1 in a:
			for i in range(len(a) - 1):
				a[i] = nod(a[i], a[i + 1])
			a.pop()
			z = z + 1
		print(n + z - 1)


import math

def main():
	n = int(input())
	A = list(map(int, input().split()))
	tmp = A[0]
	oneCnt = 0
	for i in A:
		tmp = math.gcd(tmp, i)
		oneCnt += i == 1
	if tmp != 1:
		print(-1)
		return
	if oneCnt > 0:
		print(n - oneCnt)
		return
	ans = 10 ** 8
	for i in range(n):
		tmp = A[i]
		for j in range(i, n):
			tmp = math.gcd(tmp, A[j])
			if tmp == 1:
				ans = min(ans, j - i)
	print(ans + n - 1)

def __starting_point():
	main()
__starting_point()


import sys
import fractions
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
one_count = 0
for v in data:
	if v == 1:
		one_count += 1
if one_count > 0:
	print(n - one_count)
else:
	ans = -1
	for i in range(0, n):
		v = data[i]
		for j in range(i + 1, n):
			v = fractions.gcd(v, data[j])
			if v == 1:
				cand = j - i + n - 1
				if ans == -1 or cand < ans:
					ans = cand
	print(ans)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
t = False
(l, r) = (-1, -1)
if 1 in a:
	print(n - a.count(1))
	exit(0)
ll = a[0]
for i in range(n):
	ll = a[i]
	for j in range(i, n):
		ll = gcd(ll, a[j])
		if ll == 1:
			t = True
			if abs(i - j) + 1 < r - l + 1 or r == -1:
				(r, l) = (max(i, j), min(i, j))
if not t:
	print(-1)
	exit(0)
print(n + r - l - 1)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
m = a.count(1)
if m > 0:
	print(n - m)
	exit()
ans = -1
for i in range(n):
	d = a[i]
	c = i
	for j in range(i + 1, n):
		d = gcd(d, a[j])
		if d == 1:
			c = j
			break
	if c > i:
		if ans < 0:
			ans = c - i + n - 1
		else:
			ans = min(ans, c - i + n - 1)
print(ans)


import math

def answer(n, A):
	count = 0
	for i in range(n):
		if A[i] == 1:
			count += 1
	if count:
		return n - count
	flag = 0
	mini = 2147483647
	for i in range(0, n):
		g = A[i]
		for j in range(i, n):
			g = math.gcd(g, A[j])
			if g == 1:
				flag = 1
				if mini > j - i:
					mini = j - i
					break
	if flag:
		return mini + n - 1
	return -1
n = int(input())
arr = list(map(int, input().split()))
print(answer(n, arr))


from math import gcd
n = int(input())
arr = list(map(int, input().split()))
cnt = arr.count(1)
if cnt != 0:
	print(n - cnt)
	exit()
dis = int(2000000000.0)
for i in range(len(arr)):
	g = arr[i]
	for j in range(i + 1, len(arr)):
		g = gcd(g, arr[j])
		if g == 1:
			dis = min(dis, j - i)
print(-1 if dis == int(2000000000.0) else n + dis - 1)


import math
n = int(input())
A = list(map(int, input().split()))
ans = n
cnt = A.count(1)
for i in range(n):
	m = A[i]
	for j in range(i + 1, n):
		m = math.gcd(m, A[j])
		if m == 1:
			ans = min(ans, j - i - 1)
if cnt > 0:
	print(n - cnt)
elif ans == n:
	print(-1)
else:
	print(n + ans)


from math import gcd
n = int(input())
lst = [int(i) for i in input().split()]
(d, i, g) = (n, -1, lst[0])
for j in range(n):
	g = gcd(g, lst[j])
	if g == 1:
		g = lst[j]
		for k in range(j, i, -1):
			g1 = gcd(g, lst[k])
			if g1 == 1:
				d = min(d, j - k)
				i = k
				break
			g = g1
if d == 0:
	print(n - lst.count(1))
elif d < n:
	print(d - 1 + n - lst.count(1))
else:
	print(-1)


from sys import stdin, stdout
n = int(input())
a = list(map(int, input().split()))

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
g = 0
cnt1 = 0
for i in range(n):
	g = gcd(g, a[i])
	if a[i] == 1:
		cnt1 += 1
if g != 1:
	print(-1)
	exit()
if cnt1 > 0:
	ans = n - cnt1
	print(ans)
	exit()
min_len = n
for i in range(n):
	g = 0
	for j in range(i, n):
		g = gcd(g, a[j])
		if g == 1:
			cur_len = j - i
			min_len = min(min_len, cur_len)
			break
ans = min_len + n - 1
print(ans)


from math import gcd
n = int(input())
data = list(map(int, input().split()))
mark = False
(l, r) = (-1, -1)
if 1 in data:
	print(n - data.count(1))
	exit(0)
gc = data[0]
for i in range(n):
	gc = data[i]
	for j in range(i, n):
		gc = gcd(gc, data[j])
		if gc == 1:
			mark = True
			if abs(i - j) + 1 < r - l + 1 or r == -1:
				(r, l) = (max(i, j), min(i, j))
if not mark:
	print(-1)
	exit(0)
print(n + r - l - 1)


import math
import sys
from bisect import bisect_right, bisect_left, insort_right
from collections import Counter, defaultdict
from heapq import heappop, heappush
from itertools import accumulate
from sys import stdout
R = lambda : map(int, input().split())
n = int(input())
arr = list(R())
md = -1
ones = arr.count(1)
if ones:
	print(n - ones)
	exit(0)
dp = [[0 for j in range(n)] for i in range(n)]
ml = n + 1
for l in range(1, n + 1):
	for i in range(n - l + 1):
		if l == 1:
			dp[i][i] = arr[i]
		else:
			dp[i][i + l - 1] = min(math.gcd(dp[i][i + l - 2], arr[i + l - 1]), math.gcd(dp[i + 1][i + l - 1], arr[i]))
		if dp[i][i + l - 1] == 1:
			ml = min(ml, l)
			break
if ml == n + 1:
	print(-1)
else:
	print(n + ml - 2)


from math import gcd

def solve(k, n, a, g):
	for i in range(n - k):
		g[i] = gcd(g[i], a[i + k])
		if g[i] == 1:
			return k
	return -1

def easy():
	n = int(input())
	a = [int(i) for i in input().split()]
	g = a[:]
	if n == 1:
		if a[0] == 1:
			print(0)
		else:
			print(-1)
	elif a.count(1) != 0:
		print(n - a.count(1))
	else:
		for i in range(n):
			cur = solve(i, n, a, g)
			if cur == i:
				print(n + cur - 1)
				break
		else:
			print(-1)
easy()


n = int(input())
t = list(map(int, input().split()))
one = 0
for j in t:
	if j == 1:
		one += 1
m = n + 1
if one > 0:
	print(n - one)
else:
	import math
	for i in range(n):
		u = t[i]
		for j in range(i + 1, n):
			u = math.gcd(u, t[j])
			if u == 1:
				m = min(m, j - i)
				break
	if m == n + 1:
		print(-1)
	else:
		print(m + n - 1)


import math

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
arr = [int(i) for i in input().split()]
ones = 0
for i in range(n):
	if arr[i] == 1:
		ones += 1
if ones > 0:
	print(n - ones)
else:
	ans = 10000000000
	for i in range(n):
		a1 = arr[i]
		count = 0
		for j in range(i + 1, n):
			a1 = gcd(a1, arr[j])
			count += 1
			if a1 == 1:
				ans = min(ans, n + count - 1)
				break
	if ans == 10000000000:
		print(-1)
	else:
		print(ans)


from math import gcd, inf
n = int(input())
a = [int(i) for i in input().split()]
cnt1 = sum((i for i in a if i == 1))
if cnt1 > 0:
	print(n - cnt1)
else:
	l = inf
	for i in range(n):
		g = a[i]
		for j in range(i, n):
			g = gcd(g, a[j])
			if g == 1:
				l = min(l, j - i + 1)
	if l == inf:
		print(-1)
	else:
		print(n - 1 + l - 1)


a = int(input())
s = list(map(int, input().split()))

def g(a, b):
	(a, b) = (max(a, b), min(a, b))
	while a % b > 0:
		(a, b) = (b, a % b)
	return b
b = 0
c = 0
for i in range(1, a):
	if g(s[i], s[i - 1]) == 1:
		b = 1
		break
if s.count(1) > 0 or b:
	b = 1
else:
	for j in range(1, a):
		for i in range(1, a):
			v = g(s[i], s[i - 1])
			if s[i] != s[i - 1]:
				if s[i] == 1:
					s[i - 1] = v
				else:
					s[i] = v
				c += 1
			if v == 1:
				b = 1
				break
		if s[-1] == 1:
			b += 1
		if b:
			break
if b or (a == 1 and s[0] == 1):
	print(c + a - s.count(1))
else:
	print(-1)


n = int(input())
a = list(map(int, input().split()))

def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	if a % b == 0:
		return b
	if a == 1 or b == 1:
		return 1
	return gcd(b, a % b)
cnt = 0
for i in range(n):
	if a[i] == 1:
		cnt += 1
if cnt > 0:
	print(n - cnt)
else:
	minimum = 10000000000.0
	for i in range(0, n):
		x = a[i]
		for j in range(i + 1, n):
			x = gcd(x, a[j])
			if x == 1:
				minimum = min(minimum, j - i + 1)
	if minimum == 10000000000.0:
		print(-1)
	else:
		print(n - 1 + (minimum - 1))


n = int(input())
a = [int(i) for i in input().split()]
least = len(a)
found = 0
count = 0
d = {}

def gcd(x, y):
	if x < y:
		(x, y) = (y, x)
	if (x, y) not in d:
		if x % y == 0:
			d[x, y] = y
		else:
			d[x, y] = gcd(y, x % y)
	return d[x, y]
for i in range(len(a)):
	l = a[i]
	if a[i] == 1:
		count += 1
	for j in range(i, min(len(a), least + i)):
		l = gcd(a[j], l)
		if l == 1:
			found = 1
			least = min(least, j - i)
if found == 0:
	print(-1)
elif count > 0:
	print(n - count)
else:
	print(least + n - 1)


import math

def slve(n, a):
	c1 = a.count(1)
	ans = 10 ** 20
	if c1 > 0:
		return n - c1
	for i in range(n):
		g = a[i]
		for j in range(i + 1, n):
			g = math.gcd(g, a[j])
			if g == 1:
				ans = min(ans, j - i)
	return -1 if ans == 10 ** 20 else n - 1 + ans
n = int(input())
a = list(map(int, input().split()))
print(slve(n, a))


n = int(input())
A = input().split()
A = [int(i) for i in A]

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
C = [n + 10000] * n
for i in range(0, n):
	B = A[:]
	j = i
	while B[i] != 1:
		j += 1
		if j >= n:
			break
		else:
			B[i] = gcd(B[i], A[j])
	if B[i] == 1:
		C[i] = j - i
	else:
		C[i] = n + 100
small = min(C)
if small == n + 100:
	print(-1)
elif small == 0:
	print(n - C.count(0))
else:
	print(n - 1 + small)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
n = int(input())
Ar = [int(x) for x in input().split()]
G = Ar[0]
for i in range(1, n):
	G = gcd(G, Ar[i])
if 1 in Ar:
	cnt = Ar.count(1)
	print(n - cnt)
elif G != 1:
	print(-1)
else:
	l = n
	for i in range(n - 1):
		G = Ar[i]
		for j in range(i + 1, n):
			G = gcd(Ar[j], G)
			if G == 1:
				l = min(l, j - i)
				break
	print(l + n - 1)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from math import sqrt, floor, factorial, gcd, log
from collections import deque, Counter, defaultdict
from itertools import permutations
from math import gcd
from bisect import bisect
input = lambda : sys.stdin.readline().rstrip('\r\n')
read = lambda : list(map(int, input().strip().split(' ')))

def solve():
	n = int(input())
	arr = read()
	one_count = arr.count(1)
	if one_count:
		print(n - one_count)
		return
	ans = 10 ** 5
	flag = 0
	for i in range(n):
		_gcd = arr[i]
		for j in range(i + 1, n):
			_gcd = gcd(_gcd, arr[j])
			if _gcd == 1:
				flag = 1
				ans = min(ans, j - i + n - 1)
				break
	print([-1, ans][flag == 1])
solve()


from math import gcd

def solve(nums, n):
	res = []
	for i in range(n - 1):
		res.append(gcd(nums[i], nums[i + 1]))
	if 1 not in res:
		if n > 1:
			return solve(res, len(res))
		elif n == 1:
			return -1
	elif 1 in res:
		return n

def main():
	n = int(input())
	nums = list(map(int, input().split(' ')))
	if 1 not in nums:
		res = solve(nums, n)
		if res == -1:
			print(-1)
		else:
			print(2 * n - res)
	else:
		print(n - nums.count(1))
main()


n = int(input())
a = [int(x) for x in input().split()]

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
if n == 1:
	print(0 if a[0] == 1 else -1)
else:
	gap = n
	for i in range(n):
		d = a[i]
		for j in range(i + 1, n):
			d = gcd(d, a[j])
			if d == 1:
				gap = min(gap, j - i)
	print(-1 if gap == n else gap + n - 1 - sum([x for x in a if x == 1]))


import math
from collections import Counter
n = int(input())
l = list(map(int, input().split()))
g = l[0]
for t in l:
	g = math.gcd(g, t)
if g != 1:
	print(-1)
else:
	k = 1e+18
	for i in range(n):
		g = 0
		for j in range(i, n):
			g = math.gcd(g, l[j])
			if g == 1:
				k = min(k, j - i)
				break
	x = Counter(l)
	no_1 = x[1]
	if no_1:
		print(n - no_1)
	else:
		print(n + k - 1)


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(1000000000.0) + 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
	while x != 1 and r + 1 < n:
		r += 1
		x = gcd(x, a[r])
	if x == 1 and r - l < seg:
		seg = r - l
print(seg + n - 1 if seg != inf else -1)


import math
n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(n):
	x = math.gcd(x, a[i])
if x > 1:
	print('-1')
else:
	cnt = 0
	if 1 in a:
		cnt = a.count(1)
		print(n - cnt)
	else:
		l = float('Inf')
		for i in range(n):
			x = a[i]
			for j in range(i + 1, n):
				x = math.gcd(x, a[j])
				if x == 1:
					l = min(l, j - i)
					break
		print(l + n - 1)


import math
n = int(input())
lis = list(map(int, input().split()))
ans = [0]
aa = lis[:]
c = k = 0
if n == 1 and lis[0] == 1:
	print(0)
	exit()
for i in lis:
	if i == 1:
		k += 1
for i in range(2000):
	tmp = aa[:]
	aa = []
	for j in range(1, len(tmp)):
		a = math.gcd(tmp[j], tmp[j - 1])
		aa.append(a)
		if a == 1:
			print(c + n - k)
			exit()
	c += 1
print(-1)


import fractions
n = int(input())
a = [int(i) for i in input().split()]
cnt = 0
ans = int(1000000000.0)
for i in range(n):
	if a[i] == 1:
		cnt += 1
if cnt == 0:
	for l in range(n):
		d = fractions.gcd(a[l], a[l])
		for r in range(l, n):
			d = fractions.gcd(d, a[r])
			if d == 1:
				ans = min(r - l + (n - 1), ans)
else:
	ans = n - cnt
if ans == int(1000000000.0):
	print(-1)
else:
	print(ans)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
onecnt = a.count(1)
if onecnt > 0:
	print(n - onecnt)
else:
	nop = 0
	flag = True
	while a.count(1) == 0:
		if len(a) - nop == 1 and a[0] != 1:
			flag = False
			break
		nop += 1
		for i in range(len(a) - nop):
			a[i] = gcd(a[i], a[i + 1])
	print([-1, nop + n - 1][flag])


a = int(input())
from math import gcd as z
b = list(map(int, input().split()))
if b.count(1):
	exit(print(a - b.count(1)))
ans = a
for i in range(a):
	g = b[i]
	for j in range(i + 1, a):
		g = z(g, b[j])
		if g == 1:
			ans = min(ans, j - i)
			break
print([a + ans - 1, -1][ans == a])


n = int(input())
ai = list(map(int, input().split()))
num = 0
ar = [[0] * n for i in range(n)]
for i in range(n):
	ar[0][i] = ai[i]
	if ai[i] == 1:
		num += 1

def gcd(i, j):
	a = ar[i][j - 1]
	b = ai[j]
	while b != 0:
		(a, b) = (b, a % b)
	ar[i + 1][j] = a
	return a
if num == 0:
	ans = -1
	for i in range(1, n):
		for j in range(i, n):
			if gcd(i - 1, j) == 1:
				ans = n - 1 + i
		if ans != -1:
			break
	print(ans)
else:
	print(n - num)


import math
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in a:
	if i == 1:
		cnt += 1
if cnt != 0:
	print(n - cnt)
else:
	choto = 9999999999
	flg = 0
	for i in range(n - 1):
		gosagu = a[i]
		for j in range(i + 1, n):
			gosagu = math.gcd(gosagu, a[j])
			if gosagu == 1:
				choto = min(choto, j - i)
				flg = 1
	if flg == 1:
		print(n - 1 + choto)
	else:
		print(-1)


import sys
sys.setrecursionlimit(3000)
n = int(input())
arr = str(input()).split()
arr = [int(i) for i in arr]
arr2 = [i for i in arr]

def getmax(a, b):
	if a > b:
		return a
	return b

def getmin(a, b):
	if a < b:
		return a
	return b

def gcd(a, b):
	minNum = getmin(a, b)
	j = minNum
	while j >= 1:
		if a % j == 0 and b % j == 0:
			return j
		j -= 1
s = 0

def findAns(myList, s):
	for i in myList:
		if i == 1:
			return s + (n - 1)
	if len(myList) == 1:
		return -1
	j = 1
	newarr = []
	while j < len(myList):
		newarr.append(gcd(myList[j], myList[j - 1]))
		j += 1
	return findAns(newarr, s + 1)
myans = n
for i in arr:
	if i == 1:
		myans -= 1
if myans != n:
	print(myans)
else:
	print(findAns(arr, s))


import math
n = int(input())
a = list(map(int, input().split()))
a1 = a.count(1)
if a1:
	print(n - a1)
	exit()
ans = n
for i in range(n):
	x = a[i]
	for j in range(i + 1, n):
		x = math.gcd(x, a[j])
		if x == 1:
			ans = min(ans, j - i)
			break
if ans != n:
	print(n + ans - 1)
else:
	print(-1)


from math import gcd
n = int(input())
a = [int(i) for i in input().split()]
cont = a.count(1)
if cont == 0:
	dp = [[0 for _ in range(n + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		dp[i][i] = a[i - 1]
	ans = 1000000000.0
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			dp[i][j] = gcd(dp[i][j - 1], a[j - 1])
			if dp[i][j] == 1:
				ans = min(ans, j - i)
	if ans == 1000000000.0:
		print(-1)
	else:
		print(n - 1 + ans)
else:
	print(n - cont)


n = int(input())
l1 = list(map(int, input().split()))
flag = -1
sz = n - l1.count(1)
if n - sz > 0:
	flag = sz
import math
for j in range(n):
	if flag != -1:
		break
	if l1.count(1) > 0:
		flag = j + sz - 1
		break
	for i in range(n - 1):
		l1[i] = math.gcd(l1[i], l1[i + 1])
	l1.pop()
	n -= 1
print(flag)


import math

def main():
	input()
	numList = list(map(int, input().split()))
	cnt = numList.count(1)
	if cnt > 0:
		print(str(len(numList) - cnt))
		return
	minimum = -1
	for L in range(0, len(numList)):
		gcdCounter = -1
		for R in range(L + 1, len(numList)):
			if R == L + 1:
				gcdCounter = math.gcd(numList[L], numList[R])
			else:
				gcdCounter = math.gcd(gcdCounter, numList[R])
			if gcdCounter == 1:
				if minimum == -1:
					minimum = R - L + (len(numList) - 1)
				else:
					minimum = min(minimum, R - L + (len(numList) - 1))
	print(minimum)
main()


n = int(input())
arr = list(map(int, input().split()))

def GCD(x, y):
	if y > 0:
		return GCD(y, x % y)
	else:
		return x
allGCD = arr[0]
for i in arr:
	allGCD = GCD(allGCD, i)
if allGCD > 1:
	print(-1)
else:
	ones = 0
	for i in arr:
		if i == 1:
			ones += 1
	if ones > 1:
		print(n - ones)
	else:
		res = 2000000000
		for i in range(n):
			tmp = arr[i]
			for j in range(i, n):
				tmp = GCD(tmp, arr[j])
				if tmp == 1:
					res = min(res, j - i)
		print(n + res - 1)


import math
n = int(input())
l = [int(i) for i in input().split()]
one = 0
for i in range(n):
	if l[i] == 1:
		one += 1
if one > 0:
	print(n - one)
elif len(l) == 1:
	print(-1)
else:
	ans = 0
	done = 0
	while done == 0:
		gcd1 = l
		gcd2 = []
		if len(gcd1) == 0:
			print(-1)
			break
		same = 1
		for i in range(len(gcd1) - 1):
			if gcd1[i] != gcd1[i + 1]:
				same = 0
			a = math.gcd(gcd1[i], gcd1[i + 1])
			if a == 1:
				done = 1
				print(len(gcd1) + ans)
				break
			gcd2.append(a)
		l = gcd2
		ans += 2
		if same == 1:
			print(-1)
			break


import traceback
import math

def main():
	N = int(input())
	nums = list(map(int, input().split()))
	ones = nums.count(1)
	if ones > 0:
		return N - ones
	ans = float('inf')
	for l in range(N - 1, -1, -1):
		gcd = nums[l]
		for r in range(l + 1, N):
			if r - l > ans:
				break
			gcd = math.gcd(gcd, nums[r])
			if gcd == 1:
				ans = min(ans, r - l)
				break
	return N - 1 + ans if ans != float('inf') else -1
try:
	ans = main()
	print(ans)
except Exception:
	traceback.print_exc()


n = int(input())
lst = [*map(int, input().split())]
if 1 in lst:
	from sys import exit
	print(n - lst.count(1))
	exit()
(item, i, res) = (lst[0], -1, 1000000000)
from math import gcd
for (j, x) in enumerate(lst):
	item = gcd(item, x)
	if item == 1:
		item = x
		for k in range(j, i, -1):
			item = gcd(item, lst[k])
			if item == 1:
				res = min(res, j - k)
				i = k
				item = lst[k + 1]
if res == 1000000000:
	print(-1)
else:
	print(n + res - 1)


import math
n = int(input())
a = []
k = 0
line = input().split()
for i in range(n):
	a.append(int(line[i]))
	if a[i] != 1:
		k += 1
	continue
ans = n
for i in range(n):
	temp = a[i]
	cur = 0
	for j in range(i + 1, n):
		cur += 1
		temp = math.gcd(temp, a[j])
		if temp == 1:
			if ans > cur:
				ans = cur
				pass
			pass
		continue
	continue
if k == 0:
	print('0')
elif ans == n:
	print('-1')
else:
	print(ans + k - 1)


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	(n,) = aj()
	A = aj()
	c = A.count(1)
	if c >= 1:
		print(n - c)
		exit(0)
	ans = float('inf')
	for i in range(n):
		p = A[i]
		t = 0
		for j in range(i + 1, n):
			p = math.gcd(p, A[j])
			t += 1
			if p == 1:
				break
		if p == 1:
			ans = min(ans, n - 1 + t)
	if ans == float('inf'):
		print(-1)
	else:
		print(ans)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
solve()


from math import gcd

def read():
	return [int(v) for v in input().split()]

def main():
	n = read()[0]
	a = read()
	g = a[0]
	cnt = a[0] != 1
	for i in range(1, n):
		g = gcd(g, a[i])
		if a[i] != 1:
			cnt += 1
	if g != 1:
		print(-1)
		return
	b = a[:]
	loops = 0
	found = False
	if cnt == n:
		while not found:
			c = []
			for i in range(len(b) - 1):
				v = gcd(b[i], b[i + 1])
				if v == 1:
					found = True
					break
				c.append(v)
			b = c
			loops += 1
		loops -= 1
	print(loops + cnt)
main()


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
n = int(input())
a = list(map(int, input().split()))
one = a.count(1)
if one > 0:
	print(n - one)
	exit()
ans = 10 ** 18
for i in range(n):
	G = 0
	for j in range(i, n):
		G = gcd(G, a[j])
		if G == 1:
			ans = min(ans, j - i + n - 1)
			break
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
d = n
i = -1
v = a[0]
for j in range(n):
	v = gcd(v, a[j])
	if v == 1:
		v = a[j]
		for k in range(j, i, -1):
			v1 = gcd(v, a[k])
			if v1 == 1:
				d = min(d, j - k)
				i = k
				break
			v = v1
if d == 0:
	ans = n - a.count(1)
elif d < n:
	ans = d - 1 + n - a.count(1)
else:
	ans = -1
print(ans)


from math import gcd

def check(val):
	for i in range(0, n, val):
		l = i
		r = min(n - 1, i + val - 1)
		pre[l] = arr[l]
		for j in range(l + 1, r + 1):
			pre[j] = gcd(pre[j - 1], arr[j])
		suf[r] = arr[r]
		for j in range(r - 1, l - 1, -1):
			suf[j] = gcd(suf[j + 1], arr[j])
	i = 0
	while True:
		if i + val - 1 >= n:
			break
		if gcd(suf[i], pre[i + val - 1]) == 1:
			return True
		i += 1
	return False

def binS():
	l = 0
	r = n + 1
	flag = False
	while l < r:
		mid = l + r >> 1
		if mid < 1:
			break
		if check(mid):
			flag = True
			r = mid
		else:
			l = mid + 1
	if flag:
		return r
	else:
		return -1
n = int(input())
arr = [int(x) for x in input().split()]
k = 0
for i in arr:
	if i == 1:
		k += 1
pre = [None] * n
suf = [None] * n
ans = binS()
if ans == 1:
	print(n - k)
elif ans == -1:
	print(-1)
else:
	print(ans - 1 + n - 1)


import math
n = int(input())
a = list(map(int, input().split()))
k = a[0]
l = 0
if a[0] == 1:
	l += 1
for i in range(1, n):
	k = math.gcd(a[i], k)
	if a[i] == 1:
		l += 1
if k > 1:
	print(-1)
elif l >= 1:
	print(n - l)
else:
	h = n
	for i in range(n):
		g = a[i]
		for j in range(i + 1, n):
			g = math.gcd(a[j], g)
			if g == 1:
				h = min(j - i - 1, h)
				break
	print(n + h)


import math
n = int(input())
l = list(map(int, input().split()))
if l.count(1):
	print(n - l.count(1))
else:
	tmp1 = n + 1
	for i in range(n):
		tmp2 = l[i]
		for j in range(n - i):
			tmp2 = math.gcd(tmp2, l[i + j])
			if tmp2 == 1:
				tmp1 = min(tmp1, j)
	if tmp1 == n + 1:
		print('-1')
	else:
		print(tmp1 + n - 1)


from fractions import gcd
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
if 1 < reduce(lambda x, y: gcd(x, y), a):
	print(-1)
elif any(map(lambda x: x == 1, a)):
	print(len(list(filter(lambda x: 1 < x, a))))
else:
	l = 0
	r = n
	while 1 < r - l:
		m = (l + r) // 2
		if any(map(lambda x: x == 1, map(lambda i: reduce(lambda x, y: gcd(x, y), a[i:i + m]), range(n - m + 1)))):
			r = m
		else:
			l = m
	print(r + n - 2)


from math import gcd
N = int(input())
List = [int(x) for x in input().split()]
One = List.count(1)
if One > 0:
	print(N - One)
else:
	Min = 10 ** 9
	for i in range(N):
		GCD = List[i]
		for j in range(i + 1, N):
			GCD = gcd(GCD, List[j])
			if GCD == 1:
				Min = min(j - i, Min)
				break
	if Min == 10 ** 9:
		print(-1)
	else:
		print(Min + N - 1)


import math
int(input())
a = [int(x) for x in input().split()]
c = 0
for i in range(len(a)):
	if a[i] == 1:
		c += 1
if c > 0:
	print(len(a) - c)
	exit()
x = 10000000
for i in range(len(a)):
	temp = a[i]
	for j in range(i + 1, len(a)):
		temp = math.gcd(a[j], temp)
		if temp == 1:
			x = min(x, j - i)
if x == 10000000:
	print('-1')
else:
	print(len(a) + x - 1)


import math

def iterArr(arr, num):
	dist = num
	for i in range(num):
		for j in range(i + 1, num):
			if math.gcd(arr[i], arr[j]) == 1:
				if j - i < dist:
					dist = j - i
	return dist
n = int(input())
arrIn = list(map(int, input().split()))
i = arrIn.count(1)
if i > 0:
	print(n - i)
else:
	dist1 = iterArr(arrIn, n)
	if dist1 == n:
		arr1 = []
		for k in range(n - 1):
			arr1.append(math.gcd(arrIn[k], arrIn[k + 1]))
		lenArr1 = len(arr1)
		dist2 = iterArr(arr1, lenArr1)
		if dist2 == lenArr1:
			print(-1)
		else:
			print(dist2 + n)
	else:
		print(n - 1 + dist1)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(n):
	if a[i] == 1:
		cnt += 1
if cnt:
	exit(print(n - cnt))
mn = int(1000000000.0)
for l in range(n):
	d = a[l]
	for r in range(l + 1, n):
		d = gcd(d, a[r])
		if d == 1:
			mn = min(r - l, mn)
if mn == int(1000000000.0):
	print(-1)
else:
	print(mn + n - 1)


import math
n = int(input())
a = list(map(int, input().split(' ')))
d = 0
count1 = 0
for _ in a:
	d = math.gcd(d, _)
	if _ == 1:
		count1 += 1
if d != 1:
	print(-1)
elif count1 > 0:
	print(n - count1)
else:
	mi = math.inf
	for i in range(len(a) - 1):
		dd = a[i]
		for j in range(i + 1, len(a)):
			dd = math.gcd(dd, a[j])
			if dd == 1:
				mi = min(mi, j - i + n - 1)
	print(mi)


import sys
read = lambda : sys.stdin.readline().strip()
readi = lambda : map(int, read().split())
from collections import *
from math import *

def gcd(a, b):
	while a != b:
		if a > b:
			a = a - b
		else:
			b = b - a
	return a
n = int(read())
nums = list(readi())
ones = nums.count(1)
if ones > 0:
	print(n - ones)
else:
	ans = None
	minimum = float('inf')
	for i in range(n):
		gc = nums[i]
		for j in range(i + 1, n):
			gc = gcd(gc, nums[j])
			if gc == 1:
				minimum = min(minimum, j - i)
				break
	if minimum != float('inf'):
		ans = minimum + (n - 1)
		print(ans)
	else:
		print(-1)


from math import gcd
n = int(input())
a = [int(e) for e in input().split()]
cnt = 0
for i in a:
	if i == 1:
		cnt += 1
dis = 666666666666
if cnt != 0:
	print(n - cnt)
else:
	for i in range(len(a)):
		g = a[i]
		for j in range(i + 1, len(a)):
			g = gcd(g, a[j])
			if g == 1:
				dis = min(dis, j - i)
	if dis == 666666666666:
		print(-1)
	else:
		print(n + dis - 1)


import math
from sys import stdin
n = int(stdin.readline().rstrip())
l = list(map(int, stdin.readline().rstrip().split(' ')))
m = min(l)
if m == 1:
	print(n - l.count(1))
else:
	mi = 9999999999
	for i in range(n):
		gcd = l[i]
		for j in range(i + 1, n):
			gcd = math.gcd(l[j], gcd)
			if gcd == 1:
				mi = min(j - i, mi)
				break
	if mi == 9999999999:
		print(-1)
	else:
		print(n + mi - 1)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	A = getInts()
	if 1 in A:
		return N - A.count(1)
	dist = 10 ** 9
	for i in range(N):
		tmpA = A[:]
		j = i + 1
		while j < N:
			tmpA[j] = math.gcd(tmpA[j - 1], tmpA[j])
			if tmpA[j] == 1:
				dist = min(j - i, dist)
				break
			j += 1
	return dist + N - 1 if dist < 10 ** 9 else -1
print(solve())


from math import gcd
n = int(input())
arr = list(map(int, input().split()))
if arr.count(1) > 0:
	print(n - arr.count(1))
	exit()
ans = float('inf')
for i in range(n):
	acc = arr[i]
	l = float('inf')
	for j in range(i + 1, n):
		acc = gcd(acc, arr[j])
		if acc == 1:
			l = j - i
			break
	ans = min(ans, l)
if ans == float('inf'):
	print(-1)
else:
	print(ans + n - 1)


import math
a = int(input())
z = list(map(int, input().split()))
if z.count(1) > 0:
	print(len(z) - z.count(1))
	exit()
mini = math.inf
for i in range(len(z)):
	ans = z[i]
	for j in range(i + 1, len(z)):
		ans = math.gcd(ans, z[j])
		if ans == 1:
			mini = min(j - i, mini)
if mini == math.inf:
	print(-1)
else:
	print(mini + len(z) - 1)


from sys import stdin, stdout
from functools import reduce
from math import gcd
n = int(input())
a = list(map(int, input().split()))
g = reduce(gcd, a)
if g != 1:
	print(-1)
	exit()
cnt1 = a.count(1)
if cnt1 > 0:
	ans = n - cnt1
	print(ans)
	exit()
min_len = n
for i in range(n):
	g = 0
	for j in range(i, n):
		g = gcd(g, a[j])
		if g == 1:
			cur_len = j - i
			min_len = min(min_len, cur_len)
			break
ans = min_len + n - 1
print(ans)


import sys
import math
import collections
from pprint import pprint
mod = 1000000007

def vector(size, val=0):
	vec = [val for i in range(size)]
	return vec

def matrix(rowNum, colNum, val=0):
	mat = []
	for i in range(rowNum):
		collumn = [val for j in range(colNum)]
		mat.append(collumn)
	return mat
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in a:
	if i == 1:
		cnt += 1
if cnt > 0:
	print(n - cnt)
	sys.exit()
ans = 10 ** 4
for i in range(n):
	g = a[i]
	for j in range(i + 1, n):
		g = math.gcd(g, a[j])
		if g == 1:
			ans = min(ans, n - 1 + j - i)
if ans == 10 ** 4:
	print(-1)
else:
	print(ans)


from functools import reduce
from math import gcd
n = int(input())
l = [*map(int, input().split())]
if reduce(gcd, l) != 1:
	print(-1)
else:
	m_dist = float('inf')
	for i in range(n):
		g = l[i]
		for j in range(i + 1, n):
			g = gcd(g, l[j])
			if g == 1:
				m_dist = min(m_dist, j - i)
				break
	if n == 1 and l[0] == 1:
		print(0)
	else:
		print(n - 1 + m_dist - l.count(1))


from math import gcd
n = int(input())
arr = list(map(int, input().split()))

def getans():
	cnt1s = arr.count(1)
	if cnt1s > 0:
		return n - cnt1s
	minlen = n
	for i in range(n):
		g = arr[i]
		for j in range(i + 1, n):
			g = gcd(g, arr[j])
			if g == 1:
				minlen = min(minlen, j - i)
				break
	if minlen == n:
		return -1
	return minlen + n - 1
print(getans())


from math import *
n = int(input())
a = list(map(int, input().split()))
now = 10 ** 9
ans = 10 ** 9
univ = 0
for i in range(n):
	k = a[i]
	flag = 0
	for j in range(i, n):
		k = gcd(a[j], k)
		if k == 1:
			flag = 1
			univ = 1
			break
	if j - i < ans and k == 1:
		ans = j - i
if 1 in a:
	print(n - a.count(1))
	exit(0)
if univ == 1:
	print(max(0, ans + (n - a.count(1) - 1)))
else:
	print(-1)


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:
		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
				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)
				break
		if flag:
			break
		else:
			i = k - l + 2
	if l == N + 1:
		print(-1)
	else:
		print(N + l - 2)
main()


import math
n = int(input())
arr = list(map(int, input().strip().split()))
gcd = arr[0]
for i in arr:
	gcd = math.gcd(i, gcd)
if gcd > 1:
	print(-1)
else:
	cnt = arr.count(1)
	if cnt > 0:
		print(n - cnt)
	else:
		mini = float('inf')
		for i in range(n - 1):
			gcd = arr[i]
			for j in range(i + 1, n):
				gcd = math.gcd(arr[j], gcd)
				if gcd == 1:
					mini = min(j - i, mini)
					break
		print(mini + n - 1)


import math, copy
from collections import defaultdict, Counter
from itertools import permutations

def fact(n):
	return 1 if n == 1 or n == 0 else n * fact(n - 1)

def prime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def inp():
	l = list(map(int, input().split()))
	return l

def main():
	n = int(input())
	l = inp()
	k = 987654
	dp = 99999999999
	ll = copy.deepcopy(l)
	for i in range(n):
		c = 0
		j = i
		v = 0
		while j < n - 1:
			k = math.gcd(l[j], l[j + 1])
			if l[j] == 1:
				v = 1
			l[j] = k
			if k == 1:
				break
			l[j + 1] = k
			j += 1
		if k == 1:
			c += j - i + 1 - v
			c += n - j - 1 - l[j + 1:].count(1)
			c += max(j - l[:j].count(1), 0)
			dp = min(dp, c)
		l = copy.deepcopy(ll)
	if ll.count(1) == n:
		print(0)
	elif dp == 99999999999:
		print(-1)
	else:
		print(dp)
import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()

def random():
	rating = 100
	rating = rating * 100
	rating = rating * 100
	print(rating)

def random():
	rating = 100
	rating = rating * 100
	rating = rating * 100
	print(rating)

def random():
	rating = 100
	rating = rating * 100
	rating = rating * 100
	print(rating)

def random():
	rating = 100
	rating = rating * 100
	rating = rating * 100
	print(rating)