Азербайджан - подготовка. Март 12
Елегантно переставлена сума
Задана послідовність з n цілих чисел {a1, a2, …, an}. Необхідно знайти таку її перестановку, для якої сума модулей різниць усіх сусідніх елементів максимальна. Цю найбільшу суму будемо називати елегантною.
Розглянемо, наприклад, послідовність {4, 2, 1, 5}. Шуканою є перестановка {2, 5, 1, 4}, а її елегантна сума дорівнює |2 – 5| + |5 – 1| + |1 – 4| = 3 + 4 + 3 = 10. Для усіх інших 24 перестановок значення елегантної суми не більше за 10.
Вхідні дані
Перший рядок містить кількість тестів t (t < 100). Кожний наступний рядок є окремим тестом. Кожний вхідний рядок починається числом n (1 < n < 51), за яким йде послідовність з n невід'ємних чисел. Кожне число в послідовності не більше за 1000.
Вихідні дані
Для кожного тесту вивести його номер та значення елегантної суми.
3 4 4 2 1 5 4 1 1 1 1 2 10 1
Case 1: 10 Case 2: 0 Case 3: 9