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.
//package com.company;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {

    public static void main(String[] args) throws IOException {
        // write your code here
        Scanner s = new Scanner(System.in);
        //   BufferedReader s=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = s.nextInt();
        int[] a = new int[n];int g=0;int c1=0;
        for (int i = 0; i < n; i++) {a[i] = s.nextInt();g=gcd(g,a[i]);if(a[i]==1) c1++;}
        if(g!=1){
            System.out.println(-1);
        }else{
            if(c1>0){
                System.out.println(n-c1);
                System.exit(0);
            }
            int min=Integer.MAX_VALUE;int flag=0;
            for(int i=0;i<n-1;i++){
                g=gcd(a[i],a[i]);int j=0;
                for(j=i+1;j<n;j++){
                    g=gcd(g,a[j]);
                    if(g==1) break;
                }
               if(g==1) min=Math.min(min,j-i);
            }
            System.out.println((min+n-1));
        }


    }

    static double power(double x, long y, int p) {
        double res = 1;
        x = x % p;
        while (y > 0) {
            if ((y & 1) == 1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    public static boolean dfs(int papa, int i, ArrayList<Integer>[] h, int[] vis) {
        vis[i] = 1;
        if (h[i] == null) return false;
        boolean f = false;
        for (Integer j : h[i]) {
            if (vis[j] == 0) {
                f = dfs(i, j, h, vis);
            }
        }
        return false;
    }

    static long max = Long.MIN_VALUE;
    static long max1 = Long.MIN_VALUE;

    public static void bfs(int i, HashMap<Integer, Integer>[] h, int[] vis, int len, int papa) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(i);

    }


    static int i(String a) {
        return Integer.parseInt(a);
    }

    static long l(String a) {
        return Long.parseLong(a);
    }

    static String[] inp() throws IOException {
        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        return s.readLine().trim().split("\\s+");
    }


    static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
}
class Student
{
 String name;int no,score;
//    String name, address;

    // Constructor
    public Student(String name, int no,int score)
    {this.name=name;this.no=no;this.score=score;


    }

    // Used to print student details in main()
    public String toString()
    {
        return this.name;
    }
}

class Sortbyroll implements Comparator<Student>
{
    // Used for sorting in ascending order of
    // roll number
    public int compare(Student a, Student b)
    {
        if(a.no!=b.no) return a.no-b.no ;else return b.score-a.score;
    }
}