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$。

题目描述

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 $ ?

输入输出格式

输入格式

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}<=10^{9} $ ) — the elements of the array.

输出格式

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

5
2 2 3 4 6

输出样例 #1

5

输入样例 #2

4
2 4 6 8

输出样例 #2

-1

输入样例 #3

3
2 6 9

输出样例 #3

4

说明

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.