| Автор: | А. Усманов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход |
Долгое время мальчик Петя коллекционировал целые числа. Сейчас в его коллекции уже N чисел. Разумеется, Петя бережно относится к своей коллекции: не разбрасывает по квартире и хранит в некоторой последовательности.
Сегодня Петя решил, что хранить числа просто так не интересно, поэтому он хочет перемешать их и получить новую последовательность.
Неровностью последовательности называется сумма модулей разности почти соседних элементов. Два элемента последовательности являются почти соседними, если их номера отличаются ровно на 2. Например, почти соседними элементами будут числа на позициях 1 и 3, 2 и 4, 3 и 5 и т.д.
Петя уже очень хорошо знает математику, поэтому он смог написать формулу для подсчета неровности: ∑N − 2i = 1|ai − ai + 2|. Теперь Петя хочет узнать минимальное значение неровности, которое можно получить для его коллекции после перестановки элементов. Вы должны ему с этим помочь.
Требуется написать программу, которая считает количество чисел в коллекции и сами числа, и вычислит минимальное значение неровности коллекции после перестановки элементов.
Первая строка содержит одно целое число N — количество чисел в коллекции Пети.
Далее следует N строк, в каждой из которых находится по одному целому числу ai — коллекция.
В единственной строке выведите ответ на задачу — минимальное значение неровности коллекции после некоторой перестановки элементов.
1 ≤ N ≤ 105
1 ≤ ai ≤ 106
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи |
|---|---|---|---|
| N | |||
| 1 | 30 | 1 ≤ N ≤ 3 | |
| 2 | 25 | 1 ≤ N ≤ 10 | 1 |
| 3 | 35 | 1 ≤ N ≤ 103 | 1-2 |
| 4 | 10 | 1 ≤ N ≤ 105 | 1-3 |
Обратите внимание, что первый и второй примеры относятся к первой подзадаче, а третий — ко второй.
В первом примере можно расположить коллекцию вот так: 3 1 2. Тогда неровность будет равна |3 − 2| = 1.
Во втором примере нет ни одной пары почти соседних элементов.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|