Problems
Elegant permuted sum
Elegant permuted sum
You will be given $n$ integers $\{a_1, a_2, ..., a_n\}$. Find a permutation of these $n$ integers so that summation of the absolute differences between adjacent elements is maximized. We will call this value the \textbf{elegant} permuted sum.
Consider the sequence $\{4, 2, 1, 5\}$. The permutation $\{2, 5, 1, 4\}$ yields the maximum summation. For this permutation $sum = |2~–~5| + |5~–~1| + |1~–~4| = 3 + 4 + 3 = 10$. Of all the $24$ permutations, you won't get any summation whose value exceeds $10$.
\InputFile
The first line is the number of test cases $t~(t < 100)$. Each case consists of a line that starts with $n~(1 < n < 51)$ followed by $n$ non-negative integers. None of the elements of the given permutation will exceed $1000$.
\OutputFile
For each test case print the case number followed by the elegant permuted sum.
Input example #1
3 4 4 2 1 5 4 1 1 1 1 2 10 1
Output example #1
Case 1: 10 Case 2: 0 Case 3: 9