Stable Array

Problem Description

Given $n$ positive integers $a_1, a_2, \dots, a_n$, in one operation for every $i$ with $1 \le i \le n$ we set $a_i = \gcd(a_i, a_{i \bmod n + 1})$.

Find the minimum number of operations needed so that $a_1 = a_2 = \dots = a_n$.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$.

Output Format

One non-negative integer: the minimum number of operations.

Sample Input

4
16 24 10 5

Sample Output

3

Constraints

$2 \le n \le 10^6$

$1 \le a_i \le 10^6$