E. AmShZ и G.O.A.T.
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем массив из $$$k$$$ целых чисел $$$c_1, c_2, \ldots, c_k$$$ ужасным, если выполняется следующее условие:

  • Пусть $$$AVG$$$ — это $$$\frac{c_1 + c_2 + \ldots + c_k}{k}$$$ (то есть среднее значение всех элементов массива, не обязательно целое). Тогда количество элементов массива, которые больше $$$AVG$$$, должно быть строго больше количества элементов массива, которые меньше $$$AVG$$$. Обратите внимание, что элементы, равные $$$AVG$$$, не учитываются.

    Например, $$$c = \{1, 4, 4, 5, 6\}$$$ является ужасным, потому что $$$AVG = 4.0$$$ и $$$5$$$-й и $$$4$$$-й элементы больше $$$AVG$$$, а $$$1$$$-й элемент меньше $$$AVG$$$.

Назовем массив из $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ плохим, если хотя бы одна из его непустых подпоследовательностей ужасна, и хорошим в противном случае.

Вам дан массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Найдите минимальное количество элементов, которые нужно удалить из него, чтобы получить хороший массив.

Массив является подпоследовательностью другого массива, если он может быть получен из него путем удаления нескольких (возможно, нуля или всех) элементов.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — размер $$$a$$$.

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

В каждом наборе входных данных для любого $$$1 \le i \lt n$$$ гарантируется, что $$$a_i \le a_{i+1}$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите минимальное количество элементов, которые нужно удалить из него, чтобы получить хороший массив.

Пример
Входные данные
4
3
1 2 3
5
1 4 4 5 6
6
7 8 197860736 212611869 360417095 837913434
8
6 10 56026534 405137099 550504063 784959015 802926648 967281024
Выходные данные
0
1
2
3
Примечание

В первом примере массив $$$a$$$ уже хороший.

Во втором примере достаточно удалить $$$1$$$, получив массив $$$[4, 4, 5, 6]$$$, который является хорошим.