Задан массив из положительных целых чисел \(a = [a_0, a_1, \dots, a_{n - 1}]\) (\(n \ge 2\)).
За один шаг массив \(a\) заменяется на другой массив длины \(n\), в котором каждый элемент это наибольший общий делитель (НОД) двух соседних элементов (самого элемента и его правого соседа; считайте, что правый сосед \((n - 1)\)-го элемента это \(0\)-й элемент).
Формально говоря, по массиву \(a = [a_0, a_1, \dots, a_{n - 1}]\) строится новый массив \(b = [b_0, b_1, \dots, b_{n - 1}]\) такой, что \(b_i\) \(= \gcd(a_i, a_{(i + 1) \mod n})\), где \(\gcd(x, y)\) — это наибольший общий делитель \(x\) и \(y\), а \(x \mod y\) — это остаток от деления \(x\) на \(y\). За один шаг строится массив \(b\), а затем массив \(a\) заменяется массивом \(b\) (то есть осуществляется присваивание \(a\) := \(b\)).
Например, если \(a = [16, 24, 10, 5]\), то \(b = [\gcd(16, 24)\), \(\gcd(24, 10)\), \(\gcd(10, 5)\), \(\gcd(5, 16)]\) \(= [8, 2, 5, 1]\). Таким образом, массив \(a = [16, 24, 10, 5]\) после одного шага станет равен \([8, 2, 5, 1]\).
Для заданного массива \(a\) найдите минимальное количество шагов, после которых все значения \(a_i\) станут равными (то есть \(a_0 = a_1 = \dots = a_{n - 1}\)). Если изначально массив \(a\) уже состоял из одинаковых элементов, то считайте, что количество шагов равно \(0\).