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 {
    static int gcd(int a, int b) {
        while (a != 0 && b != 0) {
            if (a > b) a = a % b;
            else b = b % a;
        }
        return a + b;
    }

    static void solve() throws IOException {
        int n = ni1();
        int a[] = new int[n];
        int b[] = new int[n - 1];
        rl();
        for (int i = 0; i < n; i++) a[i] = ni2();
        if (n == 1) {
            if (a[0] == 1) ans.append("0\n");
            else ans.append("-1\n");
        } else {
            int countOne = 0;
            boolean exist = false;
            for (int i = 0; i < n; i++) {
                if (a[i] == 1) {
                    countOne++;
                }
            }
            if (countOne > 0) exist = true;

            if (exist) ans.append(n - countOne).append('\n');
            else {
                for (int i = 0; i < n - 1; i++) b[i] = gcd(a[i], a[i + 1]);
                exist = false;
                for (int i = 0; i < n - 1; i++) {
                    if (b[i] == 1) {
                        exist = true;
                        break;
                    }
                }
                if (exist) {
                    ans.append(n).append('\n');
                } else {
                    int gcdAll = b[0];
                    for (int i = 1; i < n - 1; i++) gcdAll = gcd(gcdAll, b[i]);
                    if (gcdAll > 1) {
                        ans.append("-1\n");
                    } else {
                        int min = (int) 1e9;
                        for (int i = 0; i < n - 1; i++) {
                            for (int j = i + 1; j < n - 1; j++) {
                                if (gcd(b[i], b[j]) == 1) min = Math.min(j - i, min);
                            }
                        }
                        ans.append(min + n).append('\n');
                    }
                }
            }
        }

        output.write(ans.toString());
        output.flush();
        output.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().solve();
    }

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder ans = new StringBuilder();
    static String line;
    static StringTokenizer stringTokenizer;

    static int ni1() throws IOException {
        return Integer.parseInt(input.readLine());
    }

    static int ni2() throws IOException {
        return Integer.parseInt(stringTokenizer.nextToken());
    }

    static long nl1() throws IOException {
        return Long.parseLong(input.readLine());
    }

    static long nl2() {
        return Long.parseLong(stringTokenizer.nextToken());
    }

    static void rl() throws IOException {
        stringTokenizer = new StringTokenizer(input.readLine());
    }
}
