Interesting List

Problem code: ENCD03

The Problem is simple. You will be given n integers .Find an arrangement 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 re-arrangement <2 5 1 4> yields the maximum summation. For this arrangement, sum = abs(2-5) + abs(5-1) + abs(1-4) = 3+4+3 = 10. Of all the 24 different arrangements of the above list, you won t get any summation whose value exceeds 10. We will call this value, 10, the "Interesting list sum".

Input

The Input will consist of number of test cases. Each case consists of a line that starts with n. n will be greater than 1 and smaller than 51, followed by n non-negative integers separated by a single space. None of the elements of the given list will exceed 1000. Terminate the input with n=0.

Output

For each case, output the "Interesting list sum".

Example

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

Author: rscrbv
Date Added: 19-01-2010
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

Hint: A greedy problem

mangalsingh29 @ 24 Jan 2010 09:00 PM

Hint: A greedy problem

i have code running with not

ccoder4u @ 24 Jan 2010 09:10 PM

i have code running with not more than 50 lines..still it shows time exceed..im sure with correct logic applied

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions