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 {

	public static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader() {
			reader = new BufferedReader(new InputStreamReader(System.in), 32768);
			tokenizer = null;
		}

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(System.in), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}
	}

	public static void main(String[] args) {
		// InputStream inputStream = System.in; // Useful when taking input other than
		// console eg file handling // check ctor of inputReader
		InputReader scn = new InputReader();

		
		int n = scn.nextInt(), g = 0, steps = 0;
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = scn.nextInt();
			if (arr[i] == 1) {
				steps++;
			}
			if (i == 0) {
				g = arr[i];
				continue;
			}
			g = gcd(g, arr[i]);
		}

		if (g != 1 && steps != n) {
			System.out.println(-1);
			return;
		}

		if (steps != 0) {
			System.out.println(n - steps);
			return;
		}

		// for(int i = 1; i < n; i++) {
		// if(arr[i - 1] == arr[i]) {
		// continue;
		// }
		// if(gcd(arr[i - 1], arr[i]) == 1) {
		// System.out.println(n);
		// return;
		// }
		// }

		int dist = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			g = arr[i];
			for (int j = i + 1; j < n; j++) {
				g = gcd(g, arr[j]);
				if (g == 1) {
					int t = j - i;
					if (t < dist) {
						dist = t;
					}
				}
			}
		}
		System.out.println(n + dist - 1);
	}

	public static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}
}