5671: Coprime Segment
[Creator : ]
Description
Given an array of $n$ integers $a_i$. Let's say that a segment of this array $a[l..r]\ (1≤l≤r≤n)$ is good if the GCD of all numbers on this segment is $1$.
Your task is to find the shortest good segment.
求最短互质区间。互质区间:区间内所有数字的最大公约数为1。
Your task is to find the shortest good segment.
求最短互质区间。互质区间:区间内所有数字的最大公约数为1。
Input
The first line contains an integer $n\ (1≤n≤10^5)$.
The second line contains integers $a_i\ (1≤a_i≤10^{18})$.
The second line contains integers $a_i\ (1≤a_i≤10^{18})$.
Output
Print one number, the minimum length of a good segment. If there is no good segment, print $-1$.
Sample 1 Input
5
4 6 9 3 6
Sample 1 Output
3
Sample 2 Input
5
2 4 6 8 10
Sample 2 Output
-1