B. Разделение на классы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Напомним, что медиана массива $$$[a_1, a_2, \dots, a_{2k+1}]$$$ из нечетного количества элементов определяется следующим образом: пусть $$$[b_1, b_2, \dots, b_{2k+1}]$$$ — числа массива в отсортированном порядке. Тогда медиана этого массива равна $$$b_{k+1}$$$.

В классе $$$2n$$$ учеников, уровень навыков $$$i$$$-го ученика равен $$$a_i$$$. Не гарантируется, что все уровни навыков учеников различны.

Уровень навыков класса будем считать равным медиане уровней навыков учеников класса.

Как директор школы, вы хотели бы разделить всех учеников на $$$2$$$ класса так, чтобы в каждом классе было нечетное количество учеников (не делящееся на $$$2$$$). Количества учеников в классах могут быть равными или различными, на ваш выбор. Каждый ученик должен попасть ровно в один класс. Среди таких разделений вы хотите выбрать то, в котором модуль разности между уровнями навыков классов минимален.

Какой минимальный модуль разности вы можете получить?

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

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

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

Первая строка описания каждого набора входных данных содержит $$$2n$$$ целых чисел $$$a_1, a_2, \dots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — уровни навыков студентов.

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

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

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

Пример
Входные данные
3
1
1 1
3
6 5 4 1 2 3
5
13 4 20 13 2 5 8 3 17 16
Выходные данные
0
1
5
Примечание

В первом наборе входных данных примера есть лишь один способ разделить учеников — по одному в классе. Модуль разности уровней навыков будет равен $$$|1 - 1| = 0$$$.

Во втором наборе входных данных примера одним из возможных разделений является такое: сделать первый класс из учеников с уровнями навыков $$$[6, 4, 2]$$$, тогда уровень навыков этого класса будет равна $$$4$$$, и второй с $$$[5, 1, 3]$$$, тогда уровень навыков этого класса будет равна $$$3$$$. Модуль разности будет равен $$$|4 - 3| = 1$$$.

Заметим, что вы не можете разделить классы так: $$$[2, 3]$$$, $$$[6, 5, 4, 1]$$$ или $$$[]$$$, $$$[6, 5, 4, 1, 2, 3]$$$, потому что так классы содержат чётное число учеников.

$$$[2]$$$, $$$[1, 3, 4]$$$ тоже невозможно, так как студенты с навыками $$$5$$$ и $$$6$$$ не попадут ни в один класс.

В третьем наборе входных данных примера вы можете разделить следующим образом: $$$[3, 4, 13, 13, 20], [2, 5, 8, 16, 17]$$$ или $$$[3, 8, 17], [2, 4, 5, 13, 13, 16, 20]$$$. Оба разделения дают минимальный возможный модуль разности.