eolymp
bolt
Try our new interface for solving problems
Məsələlər

Элегантно переставленная сумма

Элегантно переставленная сумма

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Задана последовательность из 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ə

Giriş verilənləri #1
3
4 4 2 1 5
4 1 1 1 1
2 10 1
Çıxış verilənləri #1
Case 1: 10
Case 2: 0
Case 3: 9