Description

给定一个数组，每次操作可以选择数组中任意两个相邻的元素 $x, y$ 并将其 中的一个元素替换为 $gcd(x, y)$ ，其中 $gcd(x, y)$ 表示 $x$和 $y$ 的最大公约数。

请问最少需要多少次操作才能让整个数组只含 $1$ 。

Format

Input

输入的第一行包含一个整数 $n$ ，表示数组长度。

第二行包含 $n$ 个整数 $a_1, a_2, · · · , a_n$，相邻两个整数之间用一个空格分隔。

Output

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

Samples

3
4 6 9

4

评测用例规模与约定

对于 30% 的评测用例，$n ≤ 500 ，a_i ≤ 1000$；

对于 50% 的评测用例，$n ≤ 5000 ，a_i ≤ 10^6$；

对于所有评测用例，$1 ≤ n ≤ 100000 ，1 ≤ a_i ≤ 10^9$。