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 java.io.*;
import java.util.*;
import java.text.*;
import java.lang.*;
import java.math.BigInteger;
import java.util.regex.*;
public class Myclass {
	public static boolean visited[]=new boolean[100001];
	static ArrayList [] a=new ArrayList[100001];
	public static int level[]=new int[100001];
	public static int freq[]=new int[100001];
	public static int max=Integer.MIN_VALUE;
	public static void dfs(int n,int l)
	{
		visited[n]=true;
		level[n]=l++;
		max=Math.max(max, level[n]);
		for(int i=0;i<a[n].size();i++)
		{
			if(visited[(int) a[n].get(i)]==false)
			{
				dfs((int) a[n].get(i),l);
			}
		}
	}
	public static void main(String[] args)
	{
		InputReader in = new InputReader(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int n=in.nextInt();
		long a[]=new long[n];
		int one=0;
		for(int i=0;i<n;i++)
		{
			a[i]=in.nextLong();
			if(a[i]==1)
				one++;
		}
		if(one>0)
		{
			pw.println(n-one);
		}
		else
		{
			int min=Integer.MAX_VALUE;
			for(int i=0;i<n;i++)
			{
				long gcd=a[i];
				for(int j=i+1;j<n;j++)
				{
					gcd=GCD(gcd,a[j]);
					if(gcd==1)
						min=Math.min(min, j-i);
				}
			}
			if(min==Integer.MAX_VALUE)
				pw.println(-1);
			else
				pw.println(min+n-1);
		}
		pw.flush();
		pw.close();
	    
	}
		
		static class InputReader 
		{
		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) 
		{
			this.stream = stream;
		}
		public int snext() 
		{
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) 
			{
				curChar = 0;
				try 
				{
					snumChars = stream.read(buf);
				} 
				catch (IOException e) 
				{
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() 
	    {
			int c = snext();
			while (isSpaceChar(c)) 
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-')
		    {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do 
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong()
	    {
			int c = snext();
			while (isSpaceChar(c)) 
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-') 
			{
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do 
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n) 
		{
			int a[] = new int[n];
			for (int i = 0; i < n; i++) 
			{
				a[i] = nextInt();
			}
			return a;
		}

		public String readString()
	    {
			int c = snext();
			while (isSpaceChar(c)) 
			{
				c = snext();
			}
			StringBuilder res = new StringBuilder();
			do 
			{
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() 
		{
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do 
			{
				res.appendCodePoint(c);
				c = snext();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) 
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c) 
		{
			return c == '\n' || c == '\r' || c == -1;
		}

		public interface SpaceCharFilter
	    {
			public boolean isSpaceChar(int ch);
		}
	}
		public static long mod = 1000000007;
		public static int d;
		public static int p;
		public static int q;
		
		public static int[] suffle(int[] a,Random gen)
		{
			int n = a.length;
			for(int i=0;i<n;i++)
			{
				int ind = gen.nextInt(n-i)+i;
				int temp = a[ind];
				a[ind] = a[i];
				a[i] = temp;
			}
			return a;
		}
		
		public static void swap(int a, int b){
			int temp = a;
			a = b;
			b = temp;
		}
		
		public static HashSet<Integer> primeFactorization(int n)
		{
			HashSet<Integer> a =new HashSet<Integer>();
			for(int i=2;i*i<=n;i++)
			{
				while(n%i==0)
				{
					a.add(i);
					n/=i;
				}
			}
			if(n!=1)
				a.add(n);
			return a;
		}
		
		public static void sieve(boolean[] isPrime,int n)
		{
			for(int i=1;i<n;i++)
				isPrime[i] = true;
			
			isPrime[0] = false;
			isPrime[1] = false;
			
			for(int i=2;i*i<n;i++)
			{
				if(isPrime[i] == true)
				{
					for(int j=(2*i);j<n;j+=i)
						isPrime[j] = false;
				}
			}
		}
		
		public static int GCD(int a,int b)
		{
			if(b==0)
				return a;
			else
				return GCD(b,a%b);
		}
		
		public static long GCD(long a,long b)
		{
			if(b==0)
				return a;
			else
				return GCD(b,a%b);
		}
		
		public static void extendedEuclid(int A,int B)
		{
			if(B==0)
			{
				d = A;
				p = 1 ;
				q = 0;
			}
			else
			{
				extendedEuclid(B, A%B);
				int temp = p;
				p = q;
				q = temp - (A/B)*q;
			}
		}
		
		public static long LCM(long a,long b)
		{
			return (a*b)/GCD(a,b);
		}
		
		public static int LCM(int a,int b)
		{
			return (a*b)/GCD(a,b);
		}
		
		public static int binaryExponentiation(int x,int n)
		{
		    int result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=result * x;
		        x=x*x;
		        n=n/2;
		    }
		    return result;
		}
		
		public static long binaryExponentiation(long x,long n)
		{
		    long result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=result * x;
		        x=x*x;
		        n=n/2;
		    }
		    return result;
		}
		
		public static int modularExponentiation(int x,int n,int M)
		{
		    int result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=(result * x)%M;
		        x=(x*x)%M;
		        n=n/2;
		    }
		    return result;
		}
		
		public static long modularExponentiation(long x,long n,long M)
		{
		    long result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=(result * x)%M;
		        x=(x*x)%M;
		        n=n/2;
		    }
		    return result;
		}
		
		public static long modInverse(int A,int M)
		{
		    return modularExponentiation(A,M-2,M);
		}
		
		public static long modInverse(long A,long M)
		{
		    return modularExponentiation(A,M-2,M);
		}
		
		public static boolean isPrime(int n)
		{
		    
		    if (n <= 1)  return false;
		    if (n <= 3)  return true;
		    
		    if (n%2 == 0 || n%3 == 0) 
		    	return false;
		 
		    for (int i=5; i*i<=n; i=i+6)
		    {
		        if (n%i == 0 || n%(i+2) == 0)
		           return false;
		    }
		    
		    return true;
		}
		
		 public static long[] shuffle(long[] a, Random gen){ 
		        for(int i = 0, n = a.length;i < n;i++){ 
		            int ind = gen.nextInt(n-i)+i; 
		            long d = a[i]; 
		            a[i] = a[ind]; 
		            a[ind] = d; 
		        } 
		        return a; 
		    }
		static class pair implements Comparable<pair>
		{
			Long x;
			Long y;
			pair(long l,long m)
			{
				this.x=l;
				this.y=m;
			}
			

			


		public int compareTo(pair o) {
				int result = x.compareTo(o.x);
				if(result==0)
					result = y.compareTo(o.y);
				
				return result;
			}  
			
			public String toString()
			{
				return x+" "+y;
			}
			
			public boolean equals(Object o)
			{
				if (o instanceof pair)
			    {
					pair p = (pair)o;
					return p.x == x && p.y == y ;
				}
				return false;
			}
			
			public int hashCode()
			{
				return new Long(x).hashCode()*31 + new Long(y).hashCode();
			}
		}
}
