Problem Description

Given an array, in each operation you may choose any two adjacent elements $x, 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$. Find the minimum number of operations needed to make the entire array contain only $1$.

Input Format

The first line of input contains an integer $n$, which denotes the length of the array.

The second line contains $n$ integers $a_1, a_2,\dots, a_n$, separated by a single space between adjacent integers.

Output Format

Output one line containing one integer, which is the minimum number of operations. If it is impossible to meet the requirement no matter how you operate, output $-1$.

3
4 6 9

4

Hint

【Constraints and Conventions for Test Cases】

• For $30\%$ of the test cases, $n \leq 500$, $a_i \leq 1000$.
• For $50\%$ of the test cases, $n \leq 5000$, $a_i \leq 10^6$.
• For all test cases, $1 \leq n \leq 10^5$, $1 \leq a_i \leq 10^9$.

Lanqiao Cup 2022 National Contest Group A, Problem D.

Translated by ChatGPT 5