← 返回题目列表

Codeforces · 891/A

A. 骄傲

中文机器翻译题面 查看原题

你有一个长度为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。