#A2096. 最大公约数

最大公约数

题目描述

给定一个数组,每次操作可以选择数组中任意两个相邻的元素 x,yx, y 并将其中的一个元素替换为 gcd(x,y)\gcd(x, y),其中 gcd(x,y)\gcd(x, y) 表示 xxyy 的最大公约数。请问最少需要多少次操作才能让整个数组只含 11

输入格式

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

第二行包含 nn 个整数 a1,a2,,ana_1, a_2,\dots, a_n,相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数,表示最少操作次数。如果无论怎么操作都无法满足要求,输出 1-1

样例 #1

样例输入 #1

3
4 6 9

样例输出 #1

4

提示

【评测用例规模与约定】

  • 对于所有评测用例,1n1031 \leq n \leq 10^31ai1091 \leq a_i \leq 10^9