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