你有一个长度为n的数组a，你可以执行操作。每个操作是这样的:从a中选择两个相邻的元素，比如x和y，并将其中一个替换为gcd(x, y)，其中gcd表示最大公约数。 

要使所有元素都等于1，最少需要多少次操作?

输入的第一行包含一个整数n(1≤n≤2000)——数组中的元素数量。

第二行包含n个用空格分隔的整数a1, a2，…， an(1 ≤ a_i ≤ 10⁹)-数组的元素。

如果不可能将所有数字都变成1，则输出-1。否则，打印使所有数字等于1所需的最小操作次数。

样例2输入

4
2 4 6 8

样例2输出

-1

样例3输入

3
2 6 9

样例3输出

4

项海亚2021