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

public class Main{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static long mod = (long) (1e9+7);
    static final int N = 200001;
    public static List<Integer>[] edges;
	public static void main(String[] args) {
		FastReader sc = new FastReader();
	   
	    int n = sc.nextInt();
	    long[][] dp = new long[n][n];
	    int[] a = new int[n];
	    int one = 0;
	    for(int i=0;i<n;++i) {
	    	a[i] = sc.nextInt();
	    	dp[i][i] = a[i];
	    	one +=a[i] == 1 ? 1:0;
	    }
	    int ans = 0;
	    if(one > 0) {
	    	ans = n-one;
	    }else {
	    	int len = n+1,l = -1,r = -1;
	    for(int i=0;i<n;++i) {
	    	for(int j=i+1;j<n;++j) {
	    		dp[i][j] = gcd(dp[i][j-1],a[j]);
	    		if(j-i+1 < len && dp[i][j] == 1) {
	    			l = i;
	    			r = j;
	    			len = r-l+1;
	    		}
	    		
	    	}
	    }
	    if(l < 0) ans = -1;
	    else {
	    	ans = r-l + n-1;
	    }
	    
	    }
	    out.print(ans);
	    out.close();
	}
	private static long gcd(long a, long b) {
		if(b == 0) return a;
		return gcd(b,a%b);
	}


}