891A.md (1511B)
1 Source: https://codeforces.com/problemset/problem/891/A 2 3 A. Pride 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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). 22 23 What is the minimum number of operations you need to make all of the elements equal to 1? 24 25 Input 26 27 The first line of the input contains one integer *n* (1 ≤ *n* ≤ 2000) — the number of elements in the array. 28 29 The second line contains *n* space separated integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109) — the elements of the array. 30 31 Output 32 33 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. 34 35 Examples 36 37 Input 38 39 ``` 40 5 41 2 2 3 4 6 42 ``` 43 44 Output 45 46 ``` 47 5 48 ``` 49 50 Input 51 52 ``` 53 4 54 2 4 6 8 55 ``` 56 57 Output 58 59 ``` 60 -1 61 ``` 62 63 Input 64 65 ``` 66 3 67 2 6 9 68 ``` 69 70 Output 71 72 ``` 73 4 74 ``` 75 76 Note 77 78 In the first sample you can turn all numbers to 1 using the following 5 moves: 79 80 * [2, 2, 3, 4, 6]. 81 * [2, 1, 3, 4, 6] 82 * [2, 1, 3, 1, 6] 83 * [2, 1, 1, 1, 6] 84 * [1, 1, 1, 1, 6] 85 * [1, 1, 1, 1, 1] 86 87 We can prove that in this case it is not possible to make all numbers one using less than 5 moves.