자부심

길이가 n인 배열 a가 있으며, 연산을 수행할 수 있다. 각 연산은 다음과 같다. a에서 인접한 두 원소 x와 y를 선택하고, 그중 하나를 gcd(x, y)로 바꾼다. 여기서 gcd는 최대공약수를 의미한다.

모든 원소를 1로 같게 만들기 위해 필요한 최소 연산 횟수는 얼마인가?

입력의 첫 번째 줄에는 배열의 원소 개수를 나타내는 하나의 정수 n (1 ≤ n ≤ 2000)이 주어진다.

두 번째 줄에는 배열의 원소인 공백으로 구분된 n개의 정수 a1, a2, ..., an (1 ≤ ai ≤ 109)이 주어진다.

모든 수를 1로 바꾸는 것이 불가능하면 -1을 출력한다. 그렇지 않으면 모든 수를 1로 같게 만드는 데 필요한 최소 연산 횟수를 출력한다.

첫 번째 예제에서는 다음 5번의 이동으로 모든 수를 1로 바꿀 수 있다.

• $[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]$

이 경우 5번보다 적은 이동으로 모든 수를 하나로 만드는 것은 불가능함을 증명할 수 있다.