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

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел.

Будем называть медианой массива $$$q_1, q_2, \ldots, q_k$$$ число $$$p_{\lceil \frac{k}{2} \rceil}$$$, где $$$p$$$ — отсортированный по неубыванию массив $$$q$$$. Например, медиана массива $$$[9, 5, 1, 2, 6]$$$ это $$$5$$$, так как в отсортированном массиве $$$[1, 2, 5, 6, 9]$$$ число с индексом $$$\lceil \frac{5}{2} \rceil = 3$$$ это $$$5$$$, а медиана массива $$$[9, 2, 8, 3]$$$ это $$$3$$$, так как в отсортированном массиве $$$[2, 3, 8, 9]$$$ число с индексом $$$\lceil \frac{4}{2} \rceil = 2$$$ это $$$3$$$.

За одно действие вам разрешается выбрать целое число $$$i$$$ ($$$1 \le i \le n$$$) и увеличить $$$a_i$$$ на $$$1$$$.

Ваша задача найти минимальное количество действий, за которое можно увеличить медиану массива.

Обратите внимание, что в массиве $$$a$$$ необязательно все числа различны.

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

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

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

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

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

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

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

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

В первом наборе входных данных можно применить одну операцию к первому числу и получить массив $$$[3, 2, 8]$$$, у этого массива медиана равна $$$3$$$, так как это число с индексом $$$\lceil \frac{3}{2} \rceil = 2$$$ в отсортированном по неубыванию массиве $$$[2, 3, 8]$$$. У изначального массива $$$[2, 2, 8]$$$ медиана равна $$$2$$$, так как это число с индексом $$$\lceil \frac{3}{2} \rceil = 2$$$ в отсортированном по неубыванию массиве $$$[2, 2, 8]$$$. Таким образом медиана увеличилась ($$$3 > 2$$$) всего за одно действие.

В четвертом наборе входных данных можно применить по одной операции к числам с индексами $$$1, 2, 3$$$ и получить массив $$$[6, 6, 6, 4, 5]$$$, у этого массива медиана равна $$$6$$$, так как это число с индексом $$$\lceil \frac{5}{2} \rceil = 3$$$ в отсортированном по неубыванию массиве $$$[4, 5, 6, 6, 6]$$$. У изначального массива $$$[5, 5, 5, 4, 5]$$$ медиана равна $$$5$$$, так как это число с индексом $$$\lceil \frac{5}{2} \rceil = 2$$$ в отсортированном по неубыванию массиве $$$[4, 5, 5, 5, 5]$$$. Таким образом медиана увеличилась ($$$6 > 5$$$) за три действия. Можно показать, что это минимальное возможное количество действий.

В пятом наборе входных данных можно применить по одной операции к числам с индексами $$$1, 3$$$ и получить массив $$$[3, 1, 3, 3, 1, 4]$$$, у этого массива медиана равна $$$3$$$, так как это число с индексом $$$\lceil \frac{6}{2} \rceil = 3$$$ в отсортированном по неубыванию массиве $$$[1, 1, 3, 3, 3, 4]$$$. У изначального массива $$$[2, 1, 2, 3, 1, 4]$$$ медиана равна $$$2$$$, так как это число с индексом $$$\lceil \frac{6}{2} \rceil = 3$$$ в отсортированном по неубыванию массиве $$$[1, 1, 2, 2, 3, 4]$$$. Таким образом медиана увеличилась ($$$3 > 2$$$) за два действия. Можно показать, что это минимальное возможное количество действий.