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.awt.List;
		import java.io.*;
		import java.util.*;

		
		
		
		
		/*
		 * 
		 * daiict
		 *
		 * 
		 * 
		 */
		
		
		public class Main {
			FastScanner in;
			PrintWriter out;
		
			static ArrayList[] adj;
			
			static int n;
			static int m;
			static int visited[][];
			static int[][] arr;
			static int[][] brr;
			static int[][] ans;
			static int array[];
			static int pref[];
			static int sum = 0;
		//for dfs do not delete
			static int dir[][] ={{1,0},{0,1},{0,-1}};
			
			static long an = 0;
			static long bn = 0;
			static int p = 0;
			static int ta = -1;
			static int tb = -1;
			static Stack<Integer> st;
			static int k;
			static long mod = (long)1e9 + 7;
			static long[] seg;
			
			static class Pair implements Comparable<Pair>
		    {
				int x;
				boolean y;
				String s = "";
				String val;
		        Pair(int l, boolean b, String p,String q) {
		          
		        	this.x = l;
		            this.y = b;
		           this.s = p;
		           this.val = q;
		        }
		        @Override
		        public int compareTo(Pair p) {
		        	
		        	String arr[] = val.split(" ");
		        	String brr[] = p.val.split(" ");
		        	
		        	if(s.equals("numeric")){
		        		int aa = Integer.parseInt(arr[x]);
						int bb = Integer.parseInt(brr[x]);
						
						if(aa>bb && this.y){
							return 1;
						}else if(this.y){
							return -1;
						}else if(aa >= bb && ! this.y){
							return -1;
						}else{
							return 1;
						}
		        	}else{
		        		if(this.y){
		        			return arr[x].compareTo(brr[x]);
		        		}else{
		        			return brr[x].compareTo(arr[x]);
		        		}
		        	}
		            
		        }
		        
		        public String toString(){
		        	return x + " " + y;
		        }
		        
		        public boolean equals(Object o){
		        	if(o instanceof Pair){
		        		Pair a = (Pair)o;
		        		
		        		return this.x == a.x;
		        	}
		        	
		        	return false;
		        }
		        
//		        public int hashCode(){
//		        	return new Long(x).hashCode()*31 + new Long(y).hashCode();
//		        }
		    
		    }
		    
			
			public static int gcd(int a, int b) {
				if (b == 0) return a;
				return gcd(b, a%b);
			}
	
			void build(int n) {  // build the tree
				  for (int i = n - 1; i > 0; --i) seg[i] = Math.min(seg[i<<1],seg[i<<1|1]);
				}

			public static void modify(int p, long val,int n) {  // set value at position p
				  for (seg[p += n] = val; p > 1; p >>= 1) seg[p>>1] = Math.min(seg[p],seg[p^1]);
				}

				long query(int l, int r,int n) {  // sum on interval [l, r)
				  long res = Long.MAX_VALUE;
				  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
				    if ((l&1) == 1) res = (long) Math.min(res,seg[l++]);
				    if ((r&1) == 1) res = (long)Math.min(res,seg[--r]);
				  }
				  return res;
				}

				 static long bC(int n, int k)
				    {
				    long C[][] = new long[n+1][k+1];
				    int i, j;
				     
				        // Calculate  value of Binomial Coefficient in bottom up manner
				    for (i = 0; i <= n; i++)
				    {
				        for (j = 0; j <= Math.min(i, k); j++)
				        {
				            // Base Cases
				            if (j == 0 || j == i)
				                C[i][j] = 1;
				      
				            // Calculate value using previosly stored values
				            else
				                C[i][j] = C[i-1][j-1] + C[i-1][j];
				          }
				     }
				      
				    return C[n][k];
				    }
				
		    void solve() throws NumberFormatException, IOException {
		 
		    	Scanner in = new Scanner(System.in);
		    	
		    	ArrayList<Integer> list = new ArrayList<Integer>();
				ArrayList<Integer> temp = new ArrayList<Integer>();
				int n = in.nextInt();
				int arr[] = new int[n];
				int gcd=0, ones=0;
				
				for(int i=0; i<n; i++){
					arr[i] = in.nextInt();
					list.add(arr[i]);
					if(i==0)
						gcd = arr[i];
					else
						gcd = gcd(gcd, arr[i]);
					
					if(arr[i]==1)
						ones++;
				}
				
				if(gcd!=1){
					out.println(-1);
					return;
				}
				
				if(ones>0){
					out.println(n-ones);
					return;
				}
				
				
				boolean b = false;
				int ans=0;
				
				while(!b){
					ans++;
					for(int i=0; i<list.size()-1; i++){
						int x = gcd(list.get(i), list.get(i+1));
						if(x==1){
							b = true;
							break;
						}
						temp.add(x);
					}
					list = temp;
					temp = new ArrayList<Integer>();
				}
				
				System.out.println(ans + n-1);
		    }
		    
		   
		    public static void dfs(int i,int j,int d){
		    	
		    	System.out.println(i + " " + j + " " +d);
		    	
		    	if(d <= ans[i][j]){
		    		return;
		    	}
		    	
		    	if(i == n-1 && j == m-1){
		    		p = Math.max(p,d);
		    		ans[i][j] = p;
		    		arr = brr;
		    		return;
		    	}
		    	
		    	ans[i][j] = d;
		    	int temp = arr[i][j];
		    	arr[i][j] = 0;
		    	
		    	for(int p= 0;p<3;p++){
		    		int x = i + dir[p][0];
		    		int y = j + dir[p][1];
		    		
		    		if(x < 0 || x >=n || y < 0 || y >=m){
		    			continue;
		    		}else{
		    			
		    			dfs(x,y,d+arr[x][y]);
		    			
		    		}
		    	}
		    	//arr[i][j] = temp;
		    	
		    }
		 
		    
		    public static int Floor(int[] dp, int low, int high, long x)
		    {
		        // If low and high cross each other
		        if (low > high)
		            return -1;

		        // If last element is smaller than x
		        if (x >= dp[high])
		            return high;

		        // Find the middle point
		        int mid = (low+high)/2;

		        // If middle point is floor.
		        if (dp[mid] == x)
		            return mid;

		        // If x lies between mid-1 and mid
		        if (mid > 0 && dp[mid-1] <= x && x < dp[mid])
		            return mid-1;

		        // If x is smaller than mid, floor must be in
		        // left half.
		        if (x < dp[mid])
		            return Floor(dp, low, mid-1, x);

		        // If mid-1 is not floor and x is greater than
		        // arr[mid],
		        return Floor(dp, mid+1, high, x);
		    }
		    
		
		    public static String[] reverse(String arr[]){
		    	
		    	
		    	for(int i = 0;i<arr.length/2;i++){
		    		String temp = arr[i];
		    		arr[i] = arr[arr.length-i-1];
		    		arr[arr.length-1-i] = temp;
		    	}
		    	
		    	return arr;
		    	
		    }
			
		    static long inv(long x , long mod)
			{
				long r,y;
				for(r=1,y=mod-2;y!=0;x=x*x%mod,y>>=1)
				{
					if((y&1)==1)
						r=r*x%mod;
				
				}
				return r;
			}
		    
		 
		    public static long sum(long x){
		    	return x<10?x:x%10 + sum(x/10);
		    }
			
			public static long gcd(long x, long y) {
				if (x == 0)
					return y;
				else
					return gcd( y % x,x);
			}
		
			
			public static long pow(long x,long y,long n){
				if(y==0)
					return 1%n;
				if(y%2==0){
					long z=pow(x,y/2,n);
					return (z*z)%n;
				}
				return ((x%n)*pow(x,y-1,n))%n;
			}
			
			
			
			
			public static boolean isPrime(int n) {
				// Corner cases
				if (n <= 1)
					return false;
				if (n <= 3)
					return true;
		 
				// This is checked so that we can skip 
				// middle five numbers in below loop
				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;
			}
			
		
			void run() throws NumberFormatException, IOException {
				in = new FastScanner();
				out = new PrintWriter(System.out);
		
				solve();
		
				out.close();
			}
		
			class FastScanner {
				BufferedReader br;
				StringTokenizer st;
		
				public FastScanner() {
					br = new BufferedReader(new InputStreamReader(System.in));
				}
		
				String next() {
					while (st == null || !st.hasMoreTokens()) {
						try {
							st = new StringTokenizer(in.br.readLine());
						} catch (IOException e) {
							// TODO Auto-generated catch block
							e.printStackTrace();
						}
					}
					return st.nextToken();
				}
		
				int nextInt() {
					return Integer.parseInt(next());
				}
		
				long nextLong() {
					return Long.parseLong(next());
				}
		
				double nextDouble() {
					return Double.parseDouble(next());
				}
			}
			
			class Tri{
				
				Tri[] arr;
				
				public Tri(){
					arr = new Tri[27];
				}
				
			}
			
			
		 
		
			public static void main(String[] args) throws NumberFormatException, IOException {
				new Main().run();
			}
		}
		
		
		class Node{
			int a;
			int b;
			
		}
		
		class MyComp implements Comparator<String>{
		    
			int c = 0;
			
			MyComp(int d){
				c = d;
			}
			
			@Override
			public int compare(String a,String b) {
				
				// < == -1
				
				String arr[] = a.split(" ");
				String brr[] = b.split(" ");
				
				return arr[c].compareTo(brr[c]);
				
				
			}

			
		}
		
		class MyComp2 implements Comparator<String>{
		    
			int c = 0;
			
			MyComp2(int d){
				c = d;
			}
			
			@Override
			public int compare(String a,String b) {
				
				// < == -1
				
				String arr[] = a.split(" ");
				String brr[] = b.split(" ");
				
				int aa = Integer.parseInt(arr[c]);
				int bb = Integer.parseInt(brr[c]);
				
				if(aa>bb){
					return 1;
				}else{
					return -1;
				}
				
				
			}

			
		}
		
