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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author sarthakmanna
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        FastWriter out = new FastWriter(outputStream);
        CPride solver = new CPride();
        solver.solve(1, in, out);
        out.close();
    }

    static class CPride {
        long gcd(long a, long b) {
            return b == 0 ? a : gcd(b, a % b);
        }

        public void solve(int testNumber, FastReader in, FastWriter out) {
            int i, j, k;
            long g = 0;
            int oneCount = 0;

            int N = in.nextInt();
            long[] A = new long[N];
            for (i = 0; i < N; ++i) {
                A[i] = in.nextLong();
                if (A[i] == 1) ++oneCount;
                g = gcd(g, A[i]);
            }

            if (g > 1) out.println(-1);
            else {
                int ans = Integer.MAX_VALUE >> 2;
                for (i = 0; i < N; ++i) {
                    g = A[i];
                    if (A[i] == 1) ans = Math.min(ans, N - oneCount);
                    for (j = i; j < N; ++j) {
                        g = gcd(g, A[j]);
                        if (g == 1) {
                            ans = Math.min(ans, j - i + N - 1);
                        }
                    }
                }
                out.println(Math.max(0, ans));
            }

            out.flush();
        }

    }

    static class FastReader {
        static private byte[] buf = new byte[2048];
        static private int index;
        static private int total;
        static private InputStream in;

        public FastReader(InputStream is) {
            try {
                in = is;
            } catch (Exception e) {
            }
        }

        private int scan() {
            try {
                if (index >= total) {
                    index = 0;
                    total = in.read(buf);
                    if (total <= 0)
                        return -1;
                }
                return buf[index++];
            } catch (Exception e) {
                return 7 / 0;
            }
        }

        public int nextInt() {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+')
                c = scan();
            for (; c >= '0' && c <= '9'; c = scan())
                val = (val << 3) + (val << 1) + (c & 15);
            return neg ? -val : val;
        }

        public long nextLong() {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+')
                c = scan();
            for (; c >= '0' && c <= '9'; c = scan())
                val = (val << 3) + (val << 1) + (c & 15);
            return neg ? -val : val;
        }

    }

    static class FastWriter {
        static private BufferedWriter bw;

        public FastWriter(OutputStream os) {
            bw = new BufferedWriter(new OutputStreamWriter(os));
        }

        public FastWriter(Writer w) {
            bw = new BufferedWriter(w);
        }

        public void print(Object a) {
            try {
                bw.write(a.toString());
            } catch (Exception e) {
            }
        }

        public void println(Object a) {
            print(a);
            print("\n");
        }

        public void flush() {
            try {
                bw.flush();
            } catch (Exception e) {
            }
        }

        public void close() {
            try {
                bw.close();
            } catch (Exception e) {
            }
        }

    }
}

