CF891A Pride

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

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

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.