Strength
Турнир за Купата на Декана, 2010
Time Limit: 0.1s, Memory Limit: 64MiB
В някои от предметите в университета, лекторите дават на студентите да пишат проекти по двойки. За съжаление, не всички студенти са еднакво добри в даден предмет. "Силата" на даден екип е равна на това колко добър е единият човек от екипа плюс това колко добър е другият човек от екипа в дадения предмет.

Понякога се получава така, че ако има някой много добър екип, лекторът пише по-ниски оценки на тези след него, тъй като техните проекти не изглеждат толкова впечатляващи. За да не се получава това, Ели предложи на колегите си да се групират по такъв начин по двойки, че разликата между най-силния и най-слабия екип да е минимална. Ако знаете колко добър е всеки от студентите, можете ли да намерите колко ще е тази разлика?
Вход
На първия ред на стандартния вход ще бъде зададено едно четно цяло число N, указващо колко човека има в потока на Ели. На следващия ред ще има N на брой цели числа A1, A2, ..., AN, указващи колко добър е всеки студент по дадения предмет.
Изход
На стандартния изход изведете едно цяло число – колко ще бъде разликата между силите на най-силния и най-слабия екип при оптимално разпределение на студентите.
Ограничения
  • 2 ≤ N ≤ 1,000
  • 1 ≤ Ai ≤ 1,000
  • N ще бъде четно
Примерен Вход Примерен Изход
4 2 6 4 3 1
14 5 1 8 8 13 7 6 2 1 9 5 11 3 4 3
В първия пример най-доброто разпределение би било при отбори (2, 6) и (4, 3), което води до разлика 8 – 7 = 1. Във втория тест оптималното разпределение би довело до разлика 3.
Мрън!