CF891A Pride

## 问题描述 你有一个长度为 $n$ 的数列 $a$，你能执行一些操作。每个操作是这样的：选择两个相邻的数 $x$ 和 $y$，把它们中的一个换为 $\gcd(x,y)$。这里的 $\gcd$ 代表[最大公约数](en.wikipedia.org/wiki/Greatest_common_divisor)。 问你把数列中的数全变成 $1$ 的最小操作次数。

第一行是一个整数 $n$（$1 \leq n \leq 2000$）——数列中数的个数。 第二行包含 $n$ 个分开的整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 10^9$）——这个数列。

如果不可能全变成 $1$，输出 $-1$。否则，输出把数列中的数全变成 $1$ 的最小操作次数。

在第一个例子中你可以把数都变成 $1$ 通过这 $5$ 步： - $[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$。