ELPESUM - Elegant Permuted Sum

no tags 

Special Thanks: Jane Alam Jan
*At moment in University of Texas at San Antonio - USA

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, output the case number followed by the elegant permuted summation.

Example

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

hide comments
sidthe1: 2016-12-23 11:00:01

why WA?

Anant Upadhyay: 2016-07-14 14:24:34

Just pen and paper and done !

ASHUTOSH DWIVEDI: 2016-07-14 12:26:02

Logic is little bit like IMBA the problem asked in hackerrank countercode 2015

Piyush Kumar: 2016-07-12 18:02:09

There's a very elegant and easy to see nlogn solution. I wonder why the limits on n is so less.

@Sarthat Gupta: It is mentioned in the description that A[i]<=1000

Last edit: 2016-07-12 18:02:59
sarthak gupta: 2016-03-31 14:34:27

what is the range of An?

xpshekhar: 2015-12-30 21:15:11

there is no tricky case.
be careful in doing for odd numbers.

Rahul yadav: 2015-09-22 18:15:04

can anybody give more test cases (tricky) with answer

Vikneshwar E: 2015-09-21 07:09:12

[code redacted] I feel that my approach is correct. But I don't know why my solution is not accepted. Could someone please help me by providing test cases ?

Edit : AC

Last edit: 2015-12-06 16:28:29

Added by:noname
Date:2015-09-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:By Sohel Hafiz Bangladesh*