题目描述
给定一个数组，每次操作可以选择数组中任意两个相邻的元素 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。
比赛公告
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！
不准作弊！！！