给定一个数组，每次操作可以选择数组中任意两个相邻的元素 x, y 并将其中的一个元素替换为 gcd(x, y) ，其中 gcd(x, y) 表示 x 和 y 的最大公约数。

请问最少需要多少次操作才能让整个数组只含 1 。

输入的第一行包含一个整数 n ，表示数组长度。

第二行包含 n 个整数 a₁, a₂, · · · , a_n，相邻两个整数之间用一个空格分隔。

3
4 6 9

4

对于 30% 的评测用例，n ≤ 500 ，a_i ≤ 1000；

对于 50% 的评测用例，n ≤ 5000 ，a_i ≤ 10⁶；

对于所有评测用例，1 ≤ n ≤ 100000 ，1 ≤ a_i ≤ 10⁹。