Queue Data Structure
Елегантно переставлена сума
Задана послідовність з n цілих чисел \{a_1, a_2, ..., a_n\}. Необхідно знайти таку її перестановку, для якої сума модулей різниць усіх сусідніх елементів максимальна. Цю найбільшу суму будемо називати елегантною.
Розглянемо, наприклад, послідовність \{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