给定一个数组，每次操作可以选择数组中任意两个相邻的元素 x, y 并将其中的一个元素替换为 gcd(x, y) ，其中 gcd(x, y) 表示 x 和 y 的最大公约数。
请问最少需要多少次操作才能让整个数组只含 1 。
输入的第一行包含一个整数 n ，表示数组长度。
第二行包含 n 个整数 a1, a2, · · · , an，相邻两个整数之间用一个空格分隔。
输出一行包含一个整数，表示最少操作次数。如果无论怎么操作都无法满足要求，输出 −1 。
3 4 6 9
4
对于 30% 的评测用例，n ≤ 500 ，ai ≤ 1000；
对于 50% 的评测用例，n ≤ 5000 ，ai ≤ 106；
对于所有评测用例，1 ≤ n ≤ 100000 ，1 ≤ ai ≤ 109。