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.

Difficulty: competition

Starter code:

Solutions:
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)    

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)

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):
	# forward
	v = gcd(v, a[j])
	if v == 1:
		v = a[j]
		# backward
		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
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)


from math import gcd

n=int(input())
a=list(map(int,input().split()))
m=a.count(1)
if m>0:
    print(n-m)
    return
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 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)


n=int(input())
a=[int(i) for i in input().split()]
from math import gcd
g=a[:]
def solve(k):
    for i in range(n-k):
        g[i]=gcd(g[i],a[i+k])
        if g[i]==1:
            return k
    return -1
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)
        if cur==i:
            print(n+cur-1)
            break
    else:
        print(-1)


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()


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()


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())
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)

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)

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

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()

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 = 1e9
  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 == 1e9:
    print(-1)
  else:
    print(n-1+ans)
else:
  print(n-cont)

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

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


from math import gcd
n = int(input())
l = [int(i) for i in input().split(" ")]

x = l.count(1)

result = 10e9 + 5
if x > 0:
    print(n - x)
    return
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 == 10e9 + 5:
    print(-1)
else:
    print(n + result - 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)


def __starting_point():
    main()

__starting_point()

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)



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())

n=int(input())
l=list(map(int,input().split()))
cnt=l.count(1)
if cnt>0:
    print(n-cnt)
    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)


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)


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)
                if result == 1:
                    break
            cnt += 1
    if result == n + 1:
        print(-1)
    else:
        print(result + 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)



# Made By Mostafa_Khaled