Minimum Operations to Achieve an Array of Ones

You are given an array of n positive integers. In one operation, you can choose any two adjacent elements x and y in the array and replace one of them with \(\gcd(x,y)\), where \(\gcd(x,y)\) denotes the greatest common divisor of \(x\) and \(y\). The goal is to make every element in the array equal to 1 using the minimum number of operations.

Note: The \(\gcd\) function is defined in the usual way. If at least one element is already 1, you can use that value to make all other elements 1. Otherwise, you must first create a 1 by finding a contiguous subarray whose overall \(\gcd\) is 1.

Input: The first line contains a single integer n (1 \(\le\) n \(\le\) 2000), the number of elements in the array. The second line contains \(n\) positive integers.

Output: Output a single integer — the minimum number of operations needed to transform the array into an array of ones. If it is impossible, output -1.

inputFormat

The input consists of two lines. The first line contains a single integer n, the number of elements in the array. The second line contains n space-separated positive integers.

outputFormat

Output a single integer representing the minimum number of operations to make the entire array consist only of 1's. If it is impossible, output -1.

sample

3
1 2 3

2