稳定数组

题目描述

给定 $n$ 个正整数 $a_1,a_2,\dots ,a_n$，每次操作对所有的 $i,1\leq i \leq n$,令 $a_i=gcd(a_i,a_{i\% n+1})$，求最少执行多少次操作，使得 $a_1=a_2=\dots =a_n$

输入格式

第一行一个正整数 $n$

第二行 $n$ 个正整数 $a_1,a_2,\dots ,a_n$

输出格式

一个非负整数，表示最少操作数

样例输入

4
16 24 10 5

样例输出

3

数据范围

$2\leq n \leq 10^6$

$1\leq a_i \leq 10^6$