beecrowd | 1055

# Elegant Permuted Sum

By Sohel Hafiz Bangladesh*

Timelimit: 1

You will be given n integers A1A2A3...An. 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.

## Input

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.

## Output

For each case, show the case number followed by the elegant permuted summation.

 Input Sample Output Sample 3 4 4 2 1 5 4 1 1 1 1 2 10 1 Case 1: 10 Case 2: 0 Case 3: 9