В честь окончания учебного года, на кружках по программированию решили провести командный турнир. Всего в кружках занимаются 𝑛 учащихся. Им необходимо разделиться на команды по два человека в каждой. К счастью, число 𝑛 оказалось четным, поэтому получилось поделиться так, что у каждого есть команда. Чтобы соревнования были более честными, учителя решили поделить всех учащихся таким образом, чтобы силы всех команд были по возможности равными.
Всех учащихся оценили некоторым числом 𝑎, которое показывает сколько задач он смог решить в течении учебного года. Силу команды определили равной сумме силе ее участников.
Напишите программу, которая бы определяла минимальную разницу между максимальной и минимальной силой полученных команд.
Формат входных данных
Первая строка содержит число 𝑛 (4 ≤ 𝑛≤ 100, 𝑛 — четное). Вторая строка содержит 𝑛 чисел 𝑎𝑖 (1 ≤ 𝑎𝑖 ≤ 1000).
Формат выходных данных
Выведите одно число — минимально возможную разность между силами самой сильной и самой слабой команды.
Примечание
В первом примере можно разделить ребят на команды 10+2 и 4+6. Сила первой команды будет 12, а второй — 10, разница сил будет равна 2.
Во втором примере можно поделиться как угодно, сила всех команд будет равна 2, кроме одной, у которой сила будет равна 10. Таким образом, разница будет равна 8.
Во третьем примере можно поделиться на команды 1+3 и 2+2, сила обеих команд будет равна 4, разница будет равна 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
10 4 2 6
|
2
|
|
2
|
10
1 1 1 9 1 1 1 1 1 1
|
8
|
|
3
|
4
3 1 2 2
|
0
|