C. Тройка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ из $$$n$$$ элементов $$$a_1, a_2, \ldots, a_n$$$.

Вы можете выполнить следующую операцию любое количество раз (возможно, $$$0$$$):

  • Выберите два целых числа $$$i$$$ и $$$j$$$, где $$$1 \le i, j \le n$$$, и присвойте $$$a_i := a_j$$$.

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

  • Для каждой попарно различной тройки индексов $$$(x, y, z)$$$ ($$$1 \le x, y, z \le n$$$, $$$x \ne y$$$, $$$y \ne z$$$, $$$x \ne z$$$) существует невырожденный треугольник со сторонами длиной $$$a_x$$$, $$$a_y$$$ и $$$a_z$$$, т.е. $$$a_x + a_y > a_z$$$, $$$a_y + a_z > a_x$$$ и $$$a_z + a_x > a_y$$$.
Входные данные

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

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

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

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

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

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

Пример
Входные данные
4
7
1 2 3 4 5 6 7
3
1 3 2
3
4 5 3
15
9 3 8 1 6 5 3 8 2 1 4 2 9 4 7
Выходные данные
3
1
0
8
Примечание

В первом наборе входных данных одна из возможных последовательностей операций может быть следующей:

  • Присвоить $$$a_1 := a_4 = 4$$$. Массив станет $$$[4, 2, 3, 4, 5, 6, 7]$$$.
  • Присвоить $$$a_2 := a_5 = 5$$$. Массив станет $$$[4, 5, 3, 4, 5, 6, 7]$$$.
  • Присвоить $$$a_7 := a_1 = 4$$$. Массив станет $$$[4, 5, 3, 4, 5, 6, 4]$$$.

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

Во втором наборе входных данных мы можем присвоить $$$a_1 := a_2 = 3$$$, чтобы получить массив $$$a = [3, 3, 2]$$$.

В третьем наборе входных данных, поскольку $$$3$$$, $$$4$$$ и $$$5$$$ являются допустимыми длинами сторон треугольника, нам не нужно выполнять никаких операций с массивом.