Задана последовательность из целых чисел . Необходимо найти такую ее перестановку, для которой сумма модулей разниц всех соседних элементов максимальна. Эту наибольшую сумму будем называть элегантной.
Рассмотрим, например, последовательность . Искомой является перестановка , а ее элегантная сумма равна . Для всех других перестановок значение элегантной суммы не больше .
Первая строка содержит количество тестов . Каждая следующая строка является отдельным тестом. Каждая входная строка начинается числом , за которым следует последовательность из неотрицательных чисел. Каждое число в последовательности не больше .
Для каждого теста вывести его номер и значение элегантной суммы.