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.PrintWriter;
import java.io.InputStream;

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

	static class TaskC {
		static long gcd(long a, long b) {
			if (a < b) return gcd(b, a);
			while (b > 0) {
				long c = a % b;
				a = b;
				b = c;
			}
			return a;
		}

		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			int n = in.nextInt();
			long[] a = in.nextLongs(n);
			if (n == 1) {
				if (a[0] != 1) out.println(-1);
				else out.println(0);
				return;
			}
			long compound = gcd(a[0], a[1]);
			for (int i = 2; i < n; ++i) {
				compound = gcd(compound, a[i]);
			}
			if (compound != 1) {
				out.println(-1);
				return;
			}

			int onecount = 0;
			for (int i = 0; i < n; ++i) if (a[i] == 1) ++onecount;

			if (onecount == 0) {
				TaskC.CAST cast = new TaskC.CAST(n);
				for (int i = 0; i < n; ++i)
					cast.t[i + n] = a[i];

				cast.build();
				int minToGetOne = Integer.MAX_VALUE;
				for (int i = 0; i < n; ++i) {
					for (int j = i + 1; j <= n; ++j) {
						int len = j - i - 1;
						if (len < minToGetOne && cast.query(i, j) == 1) {
							minToGetOne = len;
//                        out.printf("%d %d : %d\n", i, j, minToGetOne);
						}
					}
				}

				out.println(minToGetOne + n - 1);
			} else {
				out.println(n - onecount);
			}
		}

		static class CAST {
			int n;
			long[] t;

			public CAST(int size) {
				t = new long[(n = size) << 1];
			}

			void build() {
				for (int i = n - 1; i > 0; --i) t[i] = gcd(t[i << 1], t[i << 1 | 1]);
			}

			long query(int l, int r) {
				long res = t[l + n];
				for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
					if ((l & 1) != 0) res = gcd(res, t[l++]);
					if ((r & 1) != 0) res = gcd(res, t[--r]);
				}
				return res;
			}

		}

	}

	static class FastScanner {
		private byte[] buffer = new byte[1 << 10];
		private int bp;
		private int br;
		private InputStream is;
		private boolean empty;
		private boolean skipLF;

		public FastScanner(InputStream in) {
			is = in;
		}

		private byte r() {
			if (empty) throw new UnknownError();
			if (bp == br) try {
				br = is.read(buffer, bp = 0, 1 << 10);
				if (br == -1) buffer[0] = -1;
			} catch (Exception e) {
			}
			if (bp >= buffer.length || buffer[bp] == -1) {
				empty = true;
				return -1;
			}
			return buffer[bp++];
		}

		private byte rnw() {
			skipLF = false;
			byte c;
			do c = r(); while (c <= ' ');
			return c;
		}

		public int nextInt() {
			int ret = 0;
			byte c = rnw();
			boolean neg = c == '-';
			if (neg) c = r();
			do ret = ret * 10 + c - '0'; while ((c = r()) >= '0' && c <= '9');
			if (neg) return -ret;
			return ret;
		}

		public long nextLong() {
			long ret = 0;
			byte c = rnw();
			boolean neg = c == '-';
			if (neg) c = r();
			do ret = ret * 10 + c - '0'; while ((c = r()) >= '0' && c <= '9');
			if (neg) return -ret;
			return ret;
		}

		public long[] nextLongs(int count) {
			long[] xs = new long[count];
			for (int i = 0; i < count; i++) {
				xs[i] = nextLong();
			}
			return xs;
		}

	}
}

