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.

/*


        HARSH KHATRI
        DA-IICT

                      */

import java.io.*;
import java.util.*;
import java.lang.*;
import java.util.Scanner;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class CF892C {

    static FasterScanner in = new FasterScanner();
    static PrintWriter out = new PrintWriter(System.out);
    static boolean debug = false;

    static long GCD(long a, long b) {
        a = Math.abs(a);
        b = Math.abs(b);
        if(b==0) return a;
        else return GCD(b, (a%b) );
    }

    public static void main(String[] args) {

        int n = in.nextInt(), a[] = in.nextIntArray(n);
        int i, j, k = 0;
        long g = (long)1e12, tmp;

        for(i=0; i<n; i++) {
            tmp = a[i];
            if(a[i]==1) k++;
            for(j=i+1; j<n; j++) {
                tmp = GCD(tmp, a[j]);
                if(tmp==1) { g = Math.min(g, (j-i+n-1)); break; }
            }
        }

        if(k>0) g = (n-k);
        out.println(g==(long)1e12 ? "-1" : g);
        out.close();
    }
}

class Pair implements Comparator<Pair> {

    int x;
    int y;
    int z;

    Pair() {}

    Pair(int a, int b) {
        x = a;
        y = b;
    }

    Pair(int a, int b, int c) {
        x = a;
        y = b;
        z = c;
    }

    @Override
    public int compare(Pair p, Pair q) {
        return (p.x-q.x);
    }

    @Override
    public boolean equals(Object object) {

        if(object!=null && object instanceof Pair) {
            return (this.x==((Pair)object).x && this.y==((Pair)object).y && this.z==((Pair)object).z);
        }

        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y, z);
    }
}

class FasterScanner {
    private byte[] buf = new byte[1024];
    private int curChar;
    private int snumChars;

    public int read() {
      if (snumChars == -1)
    throw new InputMismatchException();
      if (curChar >= snumChars) {
    curChar = 0;
    try {
      snumChars = System.in.read(buf);
    } catch (IOException e) {
      throw new InputMismatchException();
    }
    if (snumChars <= 0)
      return -1;
      }
      return buf[curChar++];
    }

    public double nextDouble() {
      return Double.parseDouble(this.nextString());
    }

    public String nextLine() {
      int c = read();
      while (isSpaceChar(c))
    c = read();
      StringBuilder res = new StringBuilder();
      do {
    res.appendCodePoint(c);
    c = read();
      } while (!isEndOfLine(c));
      return res.toString();
    }

    public char nextChar() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char)c;
    }

    public String nextString() {
      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 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 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 int[] nextIntArray(int n) {
      int[] arr = new int[n];
      for (int i = 0; i < n; i++) {
    arr[i] = nextInt();
      }
      return arr;
    }

    public long[] nextLongArray(int n) {
      long[] arr = new long[n];
      for (int i = 0; i < n; i++) {
    arr[i] = nextLong();
      }
      return arr;
    }

    private boolean isSpaceChar(int c) {
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private boolean isEndOfLine(int c) {
      return c == '\n' || c == '\r' || c == -1;
    }
}