SP25178 ELPESUM - Elegant Permuted Sum

Special Thanks: Jane Alam Jan \*At moment in University of Texas at San Antonio - USA You will be given **n** integers **A $ _{1} $ A $ _{2} $ A $ _{3} $ ...A $ _{n} $** . Find a permutation of these **n** integers so that summation of the absolute differences between adjacent elements is maximized. Suppose **n = 4** and the given integers are **4 2 1 5**. The permutation **2 5 1 4** yields the maximum summation. For this permutation **sum = abs(2-5) + abs(5-1) + abs(1-4) = 3+4+3 = 10**. Of all the **24** permutations, you won’t get any summation whose value exceeds **10**. We will call this value, **10**, the _elegant permuted sum_.

The first line of input is an integer **T** (**T** < 100) that represents the number of test cases. Each case consists of a line that starts with **n** (1 < **n** < 51) followed by n non-negative integers separated by a single space. None of the elements of the given permutation will exceed 1000.

For each case, output the case number followed by the _elegant permuted summation_.