Задана послідовність з 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.
Для кожного тесту вивести його номер та значення елегантної суми.