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.util.*;


import java.io.*;
 public class Solution {
		static FastScanner scr=new FastScanner();
//		static Scanner scr=new Scanner(System.in);
		static PrintStream out=new PrintStream(System.out);
		static StringBuilder sb=new StringBuilder();
		
		
		
		
		static class pair{
			int x;int y;
			pair(int x,int y){ 
				this.x=x;this.y=y;
				
			}
		}
		static class triplet{
			int x;
			long y;
			int z;
			triplet(int x,long y,int z){
				this.x=x;
				this.y=y;
				this.z=z;
			}
		}
		static class FastScanner {
			 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st=new StringTokenizer("");
		 	String next() {
		 		while (!st.hasMoreTokens())
		 			try {
		 				st=new StringTokenizer(br.readLine());
		 			} catch (IOException e) {
		 				e.printStackTrace();
		 			}
		 			return st.nextToken();
			} long gcd(long a,long b){
				if(b==0) {
					return a;
				}
					
				return gcd(b,a%b);
			}
		 	int[]  sort(int a[]) {
				 
		        int multiplier = 1, len = a.length, max = Integer.MIN_VALUE;
		        int b[] = new int[len];
		        int bucket[];
		        for (int i = 0; i < len; i++) if (max < a[i]) max = a[i];
		        while (max / multiplier > 0) {
		            bucket = new int[10];
		            for (int i = 0; i < len; i++) bucket[(a[i] / multiplier) % 10]++;
		            for (int i = 1; i < 10; i++) bucket[i] += (bucket[i - 1]);
		            for (int i = len - 1; i >= 0; i--) b[--bucket[(a[i] / multiplier) % 10]] = a[i];
		            for (int i = 0; i < len; i++) a[i] = b[i];
		            multiplier *= 10;
		        }
		        return a;
		    }
		 	 long modPow(long base,long exp) {
				if(exp==0) {
					return 1;
				}
				if(exp%2==0) {
					long res=(modPow(base,exp/2));
					return (res*res);
				}
				return (base*modPow(base,exp-1));
			}
			int []reverse(int a[]){
				int b[]=new int[a.length];
				int index=0;
				for(int i=a.length-1;i>=0;i--) {
					b[index]=a[i];
				}
				return b;
			}
			int nextInt() {
				return Integer.parseInt(next());
			}
			int[] readArray(int n) {
				int[] a=new int[n];
				for (int i=0; i<n; i++) a[i]=nextInt();
				return a;
			}
			long[] readLongArray(int n) {
				long  [] a=new long  [n];
				for (int i=0; i<n; i++) a[i]=nextLong();
				return a;
			}
			long nextLong() {
				return Long.parseLong(next());
			}
		}
		
		static void print(Object ele) {
			sb.append(ele).append(" ");
		}
		static void println(Object ele) {
			sb.append(ele).append('\n');
			
		}
		static void println() {
			sb.append('\n');
		}
//		static long LCM(long a,long b) {
//			return a*b/(scr.gcd(a, b));
//		}
//		static long n, m, k, l, q, count, sum, temp, ans;
//		static long []a;
//		static long b[];
//		static  char c[];
//		static char t[];
//		static boolean visited[][];
		static int gcd(int a,int b) {
			if(b==0) {
				return a;
			}
			return gcd(b, a%b);
			
		}
		static ArrayList<Integer>list[];
		static void solve() {
			 int n = scr.nextInt();
			 int []a=scr.readArray(n);
			 
			 int one=0;
			 for(int i=0;i<n;i++) {
				 if(a[i]==1) {
					 one++;
				 }
			 }
			 if(one!=0) {
				 out.println((n-one));
				 return;
			 }
			 
			 int size=MAX;
			 for(int i=0;i<n;i++) {
				 int gcd=a[i];
				 int j=i+1;
				 for(j=i+1;j<n && gcd!=1;j++) {
					 gcd=gcd(a[j],gcd);
				 }
				 if(gcd==1) {
					 size = Math.min(size, (j-1)-i);
				 }
			 }
			 
			 if(size==MAX) {
				 out.println(-1);
			 }else {
				 int res = n+size-1;
				 out.println(res);
			 }
		} 
		
		static int  MAX = Integer.MAX_VALUE;
		static int  MIN = Integer.MIN_VALUE;
		public static void main(String []args) {
//			int t=scr.nextInt();
//			while(t-->0) {
//				solve();
//			}
			solve();
//			out.println(sb);
		}
	}
 