Напомним, что медиана массива \([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\)). Количества учеников в классах могут быть равными или различными, на ваш выбор. Каждый ученик должен попасть ровно в один класс. Среди таких разделений вы хотите выбрать то, в котором модуль разности между уровнями навыков классов минимален.
Какой минимальный модуль разности вы можете получить?
Примечание
В первом наборе входных данных примера есть лишь один способ разделить учеников — по одному в классе. Модуль разности уровней навыков будет равен \(|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]\). Оба разделения дают минимальный возможный модуль разности.