eolymp
Змагання

Азербайджан - подготовка. Март 12

Елегантно переставлена сума

Задана послідовність з n цілих чисел {a1, a2, …, an}. Необхідно знайти таку її перестановку, для якої сума модулей різниць усіх сусідніх елементів максимальна. Цю найбільшу суму будемо називати елегантною.

Розглянемо, наприклад, послідовність {4, 2, 1, 5}. Шуканою є перестановка {2, 5, 1, 4}, а її елегантна сума дорівнює |25| + |51| + |14| = 3 + 4 + 3 = 10. Для усіх інших 24 перестановок значення елегантної суми не більше за 10.

Вхідні дані

Перший рядок містить кількість тестів t (t < 100). Кожний наступний рядок є окремим тестом. Кожний вхідний рядок починається числом n (1 < n < 51), за яким йде послідовність з n невід'ємних чисел. Кожне число в послідовності не більше за 1000.

Вихідні дані

Для кожного тесту вивести його номер та значення елегантної суми.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
4 4 2 1 5
4 1 1 1 1
2 10 1
Вихідні дані #1
Case 1: 10
Case 2: 0
Case 3: 9