CF891A.Pride

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.

What is the minimum number of operations you need to make all of the elements equal to 1?

你有一个长度为 $n$ 的数组 $a$，你可以执行若干次操作。每次操作如下：从数组 $a$ 中选择两个相邻的元素，记为 $x$ 和 $y$，并将其中某一个替换为 $\gcd(x,\,y)$，其中 $\gcd$ 表示最大公约数。

你需要执行的最少操作次数是多少，才能使数组中所有元素都等于 $1$？

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 _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — the elements of the array.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 2000$）—— 表示数组中元素的个数。

第二行包含 $n$ 个以空格分隔的整数 $a_1,\ a_2,\ \dots,\ a_n$（$1 \leq a_i \leq 10^9$）—— 表示数组的元素。

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.

如果无法将所有数字变为 1，则输出 $-1$；否则，输出使所有数字都等于 1 所需的最少操作次数。

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.

在第一个样例中，你可以通过以下 5 步操作将所有数字变为 1：

• [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]

我们可以证明：在此情况下，无法用少于 5 步的操作使所有数字都变为 1。