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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
			
				 
				public class Solution1 implements Runnable
				{
					static final int MAX = 1000000007;
					static class InputReader
					{
						private InputStream stream;
						private byte[] buf = new byte[1024];
						private int curChar;
						private int numChars;
						private SpaceCharFilter filter;
						private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
				
						public InputReader(InputStream stream)
						{
							this.stream = stream;
						}
						
						public int read()
						{
							if (numChars==-1) 
								throw new InputMismatchException();
							
							if (curChar >= numChars)
							{
								curChar = 0;
								try 
								{
									numChars = stream.read(buf);
								}
								catch (IOException e)
								{
									throw new InputMismatchException();
								}
								
								if(numChars <= 0)				
									return -1;
							}
							return buf[curChar++];
						}
					 
						public String nextLine()
						{
							String str = "";
				            try
				            {
				                str = br.readLine();
				            }
				            catch (IOException e)
				            {
				                e.printStackTrace();
				            }
				            return str;
						}
						public int nextInt()
						{
							int c = read();
							
							while(isSpaceChar(c)) 
								c = read();
							
							int sgn = 1;
							
							if (c == '-') 
							{
								sgn = -1;
								c = read();
							}
							
							int res = 0;
							do 
							{
								if(c<'0'||c>'9') 
									throw new InputMismatchException();
								res *= 10;
								res += c - '0';
								c = read();
							}
							while (!isSpaceChar(c)); 
							
							return res * sgn;
						}
						
						public long nextLong() 
						{
							int c = read();
							while (isSpaceChar(c))
								c = read();
							int sgn = 1;
							if (c == '-') 
							{
								sgn = -1;
								c = read();
							}
							long res = 0;
							
							do 
							{
								if (c < '0' || c > '9')
									throw new InputMismatchException();
								res *= 10;
								res += c - '0';
								c = read();
							}
							while (!isSpaceChar(c));
								return res * sgn;
						}
						
						public double nextDouble() 
						{
							int c = read();
							while (isSpaceChar(c))
								c = read();
							int sgn = 1;
							if (c == '-') 
							{
								sgn = -1;
								c = read();
							}
							double res = 0;
							while (!isSpaceChar(c) && c != '.') 
							{
								if (c == 'e' || c == 'E')
									return res * Math.pow(10, nextInt());
								if (c < '0' || c > '9')
									throw new InputMismatchException();
								res *= 10;
								res += c - '0';
								c = read();
							}
							if (c == '.') 
							{
								c = read();
								double m = 1;
								while (!isSpaceChar(c)) 
								{
									if (c == 'e' || c == 'E')
										return res * Math.pow(10, nextInt());
									if (c < '0' || c > '9')
										throw new InputMismatchException();
									m /= 10;
									res += (c - '0') * m;
									c = read();
								}
							}
							return res * sgn;
						}
						
						public String readString() 
						{
							int c = read();
							while (isSpaceChar(c))
								c = read();
							StringBuilder res = new StringBuilder();
							do 
							{
								res.appendCodePoint(c);
								c = read();
							} 
							while (!isSpaceChar(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;
						}
					 
						public String next() 
						{
							return readString();
						}
						
						public interface SpaceCharFilter 
						{
							public boolean isSpaceChar(int ch);
						}
					}
				 	
					public static void main(String args[]) throws Exception
					{
						new Thread(null, new Solution1(),"Solution1",1<<26).start();
					}
					
					public void run()
					{
						InputReader sc= new InputReader(System.in);
						PrintWriter w= new PrintWriter(System.out);
						int n = sc.nextInt();
						int[] arr =  new int[n];
						int count = 0; 
						int comp = 0;
						for(int i = 0;i < n;i++){
							arr[i]  =sc.nextInt();
							if(arr[i] == 1){
								count++;
							}
							if(i == 0){
								comp = arr[0];
							}
							comp = gcd(comp,arr[i]);
						}
						//w.println(comp);
						if(comp != 1){
							w.println(-1);
							w.close();
							System.exit(0);
						}
						if(count != 0){
							w.println(n - count);
						}else{
							int ans = Integer.MAX_VALUE;
							for(int i = 0;i < n;i++){
								int temp = arr[i];
								int index = -1;
								for(int j = i+1;j < n;j++){
									{
										temp = gcd(temp,arr[j]);
										if(temp == 1){
											ans = Math.min(ans,j - i);
											break;
										}
									}
								}
							}
							w.println(ans + n - 1);
						}
						w.close();
					}
					public static int gcd(int a, int b)
				    {
				        if (a == 0)
				            return b;
				         
				        return gcd(b%a, a);
				    }
					static class Pair implements Comparable<Pair>{
						int a;
						int b;
						Pair(int a,int b)	{
							this.a = a;
							this.b = b;
						}
						public boolean equals(Object o)
						{
							Pair p = (Pair)o;
							return p.a==a && p.b==b;
						}
						public int compareTo(Pair p){
							return Long.compare(this.a,p.a);
						}
						public int hashCode()
						{
							return new Long(a).hashCode()*31 + new Long(a).hashCode();
						}
					}
				}