CF891A.Pride

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

输入格式

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.

首页