Дан массив \(a\) целых чисел размера \(n\). Вы можете выполнять следующую операцию неограниченное количество раз:
- Выбрать некоторый подмассив \(a\) четного размера \(2k\), начинающийся в позиции \(l\) (\(1\le l \le l+2\cdot{k}-1\le n\), \(k \ge 1\)) и для каждого \(i\), лежащего между \(0\) и \(k-1\) (включительно), присвоить значение \(a_{l+k+i}\) элементу \(a_{l+i}\).
Например, при \(a = [2, 1, 3, 4, 5, 3]\) и выборе \(l = 1\) и \(k = 2\), проделывая описанную операцию, получим \(a = [3, 4, 3, 4, 5, 3]\).
Найдите минимальное количество операций (возможно ноль), необходимых для того, чтобы сделать все элементы массива равными друг другу.
Выходные данные
Выведите \(t\) строк, содержащих ответ к соответствующим наборам входных данных — минимальное количество операций, необходимых для того, чтобы сделать все элементы массива равными друг другу.
Примечание
В первом наборе входных данных все элементы массива равны, следовательно, никаких операций не требуется.
Во втором наборе можно выполнить операцию с \(k=1\) и \(l=1\), присвоив \(a_1 := a_2\), и массив станет равным \([1, 1]\) за \(1\) операцию.
В третьем наборе можно выполнить операцию с \(k=1\) и \(l=4\), присвоив \(a_4 := a_5\), и массив станет равным \([4, 4, 4, 4, 4]\).
В четвертом наборе можно выполнить операцию с \(k=1\) и \(l=3\), присвоив \(a_3 := a_4\) и получив массив, равный \([4, 2, 3, 3]\). Затем можно выполнить операцию с \(k=2\) и \(l=1\), присвоив \(a_1 := a_3\), \(a_2 := a_4\) и получив массив, равный \([3, 3, 3, 3]\).
В пятом наборе массив состоит только из одного элемента, поэтому никаких операций не требуется.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 1 1
2
2 1
5
4 4 4 2 4
4
4 2 1 3
1
1
|
0
1
1
2
0
|