給定一個數(shù)組，每次操作可以選擇數(shù)組中任意兩個相鄰的元素 x, y 并將其中的一個元素替換為 gcd(x, y) ，其中 gcd(x, y) 表示 x 和 y 的最大公約數(shù)。

請問最少需要多少次操作才能讓整個數(shù)組只含 1 。 

輸入的第一行包含一個整數(shù) n ，表示數(shù)組長度。

第二行包含 n 個整數(shù) a₁, a₂, · · · , a_n，相鄰兩個整數(shù)之間用一個空格分隔。 

輸出一行包含一個整數(shù)，表示最少操作次數(shù)。如果無論怎么操作都無法滿足要求，輸出 ?1 。

3
4 6 9

4

對于 30% 的評測用例，n ≤ 500 ，a_i ≤ 1000；

對于 50% 的評測用例，n ≤ 5000 ，a_i ≤ 10⁶；

對于所有評測用例，1 ≤ n ≤ 100000 ，1 ≤ a_i ≤ 10⁹。