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