你有一个长度为n的数组a,你可以执行操作。每个操作都是这样的:从 a 中选择两个相邻元素,例如 x 和 y,并将其中一个替换为 gcd(x, y),其中 gcd 表示最大公约数。
使所有元素等于 1 所需的最少运算次数是多少?
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 2000) — 数组中的元素数量。
第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109) - 数组的元素。
输出
如果不可能将所有数字变为 1,则打印 -1。否则,打印使所有数字等于 1 所需的最少运算次数。
示例
输入 #1
5 2 2 3 4 6
输出 #1
5
输入 #2
4 2 4 6 8
输出 #2
-1
输入 #3
3 2 6 9
输出 #3
4
注意
在第一个示例中,您可以使用以下 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。