← 返回题目

题库练习 Pride

← 上一题下一题 →

A11419 | $Pride$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

输入 #2

4
2 4 6 8

输出 #2

-1

输入 #3

3
2 6 9

输出 #3

C++ 编辑器

输入

输出