Вам дан циклический массив \(a_1, a_2, \ldots, a_n\).
Вы можете выполнить следующую операцию над \(a\) не более \(n - 1\) раз:
- Пусть \(m\) — текущая длина \(a\). Вы можете выбрать любые два соседних элемента, где предыдущий элемент не больше следующего (в частности, \(a_m\) и \(a_1\) являются соседними, причём \(a_m\) — предыдущий), и удалить ровно один из них. Другими словами, выберите целое число \(i\) (\(1 \leq i \leq m\)), для которого выполняется \(a_i \leq a_{(i \bmod m) + 1}\), и удалите из \(a\) либо \(a_i\), либо \(a_{(i \bmod m) + 1}\).
Ваша цель — найти минимальное количество операций, необходимых для того, чтобы сделать все элементы в \(a\) равными.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую целое число: минимальное количество операций, необходимых для того, чтобы сделать все элементы в \(a\) равными.
Примечание
В первом наборе входных данных в \(a\) есть только один элемент, поэтому мы не можем выполнить ни одной операции.
Во втором наборе входных данных мы можем выполнить следующие операции, чтобы сделать все элементы в \(a\) равными:
- выбрать \(i = 2\), удалить \(a_3\), тогда \(a\) станет \([1, 2]\).
- выбрать \(i = 1\), удалить \(a_1\), тогда \(a\) станет \([2]\).
Можно доказать, что нельзя сделать все элементы в \(a\) равными, используя менее \(2\) операций, поэтому ответ — \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
1
3
1 2 3
3
1 2 2
5
5 4 3 2 1
6
1 1 2 2 3 3
8
8 7 6 3 8 7 6 3
6
1 1 4 5 1 4
|
0
2
1
4
4
6
3
|