Задача 2. Необычная сортировка

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Долгое время мальчик Петя коллекционировал целые числа. Сейчас в его коллекции уже N чисел. Разумеется, Петя бережно относится к своей коллекции: не разбрасывает по квартире и хранит в некоторой последовательности.

Сегодня Петя решил, что хранить числа просто так не интересно, поэтому он хочет перемешать их и получить новую последовательность.

Неровностью последовательности называется сумма модулей разности почти соседних элементов. Два элемента последовательности являются почти соседними, если их номера отличаются ровно на 2. Например, почти соседними элементами будут числа на позициях 1 и 3, 2 и 4, 3 и 5 и т.д.

Петя уже очень хорошо знает математику, поэтому он смог написать формулу для подсчета неровности: N − 2i = 1|ai − ai + 2|. Теперь Петя хочет узнать минимальное значение неровности, которое можно получить для его коллекции после перестановки элементов. Вы должны ему с этим помочь.

Требуется написать программу, которая считает количество чисел в коллекции и сами числа, и вычислит минимальное значение неровности коллекции после перестановки элементов.

Пояснение

Модулем числа называется его абсолютное значение. Например, модулем числа 2 является 2, а модулем числа  − 3 является число 3. Обозначается модуль как |x|.

Формат входных данных

Первая строка содержит одно целое число N — количество чисел в коллекции Пети.

Далее следует N строк, в каждой из которых находится по одному целому числу ai — коллекция.

Формат выходных данных

В единственной строке выведите ответ на задачу — минимальное значение неровности коллекции после некоторой перестановки элементов.

Ограничения

1 ≤ N ≤ 105

1 ≤ ai ≤ 106

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
N
1301 ≤ N ≤ 3
2251 ≤ N ≤ 101
3351 ≤ N ≤ 1031-2
4101 ≤ N ≤ 1051-3

Пояснение к примерам

Обратите внимание, что первый и второй примеры относятся к первой подзадаче, а третий — ко второй.

В первом примере можно расположить коллекцию вот так: 3 1 2. Тогда неровность будет равна |3 − 2| = 1.

Во втором примере нет ни одной пары почти соседних элементов.

Примеры тестов

Стандартный вход Стандартный выход
1
3
1
2
3
1
2
2
1000000
1
0
3
5
8
2
1
9
4
4

0.073s 0.010s 15