C. Турнир
ограничение по времени на тест: 1 секунда
ограничение по памяти на тест: 512 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
В лингвистической игре «Шляпа» могут принимать участие несколько пар игроков. Также в игре должен быть ведущий.
Учитель планирует организовать турнир по «Шляпе» в своем классе, в котором учатся nn школьников, nn нечетно. Для этого он хочет разбить школьников на пары, а тот, кто останется без пары — будет ведущим.
Пронумеруем школьников целыми числами от 1 до n. Для i-го школьника известен его уровень игры в «Шляпу» — целое число a_i. Уровень игры пары равен сумме уровней игры входящих в нее двух школьников.
Чтобы турнир был как можно более справедливым, учитель хочет, чтобы разность между максимальным и минимальным уровнями получившихся пар была как можно меньше. Помогите учителю выбрать ведущего и составить из оставшихся n−1 школьников пары так, чтобы добиться поставленной цели.
Входные данные
Первая строка входных данных содержится целое число n — число учеников в классе (3≤n≤5⋅10^5, гарантируется, что n нечетно).
Вторая строка содержит n целых чисел a1,a2,…,an (1≤ai≤10^9).
Выходные данные
Выведите одно число — минимальную возможную разность между максимальным и минимальным уровнем пар в турнире.
Пример
входные данные
5
1 2 3 5 9
выходные данные
1
Дайте подсказку как решить эту задачу. Придумал решение за квадрат, где я в тупую перебираю ведущего и для каждого считаю эту минимальную разницу линейно. Затем просто нахожу минимальный среди всех.