ПОСТАНОВКА ЗАДАЧИ
Очки: 30
У Кевина есть последовательность целых чисел a1, a2, …, an. Определите силу последовательности, которая будет
|a1 — a2| + |a2 — a3| + … + |an-1 — an| + |an — a1|.
Кевин хочет усилить свою последовательность, поэтому он переупорядочивает ее в новую последовательность b1, b2, …, bn. Он хочет, чтобы эта новая последовательность была максимально сильной. Какова максимально возможная сила полученной последовательности?
Вход
Ввод состоит из 2 строк. В первой строке находится положительное целое число n. Вторая строка содержит n целых чисел a1, a2, …, an.
Вывод
Выведите одно целое число: максимально возможная сила.
Ограничения
1 <= n <= 105.
|ай| ‹= 109. Обратите внимание, что ai может быть отрицательным.
ОБРАЗЕЦ ВВОДА
4 1 2 4 8
ОБРАЗЕЦ ВЫВОДА
18
Объяснение
В примере исходная последовательность — 1, 2, 4, 8. Ее сила — |1–2| + |2–4| + |4–8| + |8–1| = 14. Если Кевин переупорядочивает его как 1, 8, 2, 4, новая сила будет |1–8| + |8–2| + |2–4| + |4–1| = 18. Это максимально возможное значение.
Ограничение по времени: 1,0 с для каждого входного файла.
Ограничение памяти: 256 МБ
Ограничение источника: 1024 КБ
Схема выставления оценок.Оценки присуждаются, если какой-либо тест проходит успешно.
РЕШЕНИЕ:
