Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

A. Сделать все равными
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан циклический массив $$$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$$$ равными.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую целое число: минимальное количество операций, необходимых для того, чтобы сделать все элементы в $$$a$$$ равными.

Пример
Входные данные
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
Примечание

В первом наборе входных данных в $$$a$$$ есть только один элемент, поэтому мы не можем выполнить ни одной операции.

Во втором наборе входных данных мы можем выполнить следующие операции, чтобы сделать все элементы в $$$a$$$ равными:

  • выбрать $$$i = 2$$$, удалить $$$a_3$$$, тогда $$$a$$$ станет $$$[1, 2]$$$.
  • выбрать $$$i = 1$$$, удалить $$$a_1$$$, тогда $$$a$$$ станет $$$[2]$$$.

Можно доказать, что нельзя сделать все элементы в $$$a$$$ равными, используя менее $$$2$$$ операций, поэтому ответ — $$$2$$$.