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.
Giriş verilənləri
Первая строка содержит количество тестов t~(t < 100). Каждая следующая строка является отдельным тестом. Каждая входная строка начинается числом n~(1 < n < 51), за которым следует последовательность из n неотрицательных чисел. Каждое число в последовательности не больше 1000.
Çıxış verilənləri
Для каждого теста вывести его номер и значение элегантной суммы.
Nümunə
3 4 4 2 1 5 4 1 1 1 1 2 10 1
Case 1: 10 Case 2: 0 Case 3: 9