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

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

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

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

3
4 6 9

4

對(duì)于 30% 的評(píng)測(cè)用例，n ≤ 500 ，a_i ≤ 1000；

對(duì)于 50% 的評(píng)測(cè)用例，n ≤ 5000 ，a_i ≤ 10⁶；

對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 100000 ，1 ≤ a_i ≤ 10⁹。