Задача №115271. Турнир
В лингвистической игре «Шляпа» могут принимать участие несколько пар игроков. Также в игре должен быть ведущий.
Учитель планирует организовать турнир по «Шляпе» в своем классе, в котором учатся \(n\) школьников, \(n\) нечетно. Для этого он хочет разбить школьников на пары, а тот, кто останется без пары — будет ведущим.
Пронумеруем школьников целыми числами от \(1\) до \(n\). Для \(i\)-го школьника известен его уровень игры в «Шляпу» — целое число \(a_i\). Уровень игры пары равен сумме уровней игры входящих в нее двух школьников.
Чтобы турнир был как можно более справедливым, учитель хочет, чтобы разность между максимальным и минимальным уровнями получившихся пар была как можно меньше. Помогите учителю выбрать ведущего и составить из оставшихся \(n-1\) школьников пары так, чтобы добиться поставленной цели.
Первая строка входных данных содержится целое число \(n\) — число учеников в классе (\(3 \le n \le 5 \cdot 10^5\), гарантируется, что \(n\) нечетно).
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).
Выведите одно число — минимальную возможную разность между максимальным и минимальным уровнем пар в турнире.
5 1 2 3 5 9
1