Martian Football Tournament

Problem code: IITI01

All submissions for this problem are available.

Freakin' news has recently claimed that they have discovered a civilization on mars and that they have established contact with the martians. Following is a summary of the breakfast hour breakin' news on freakin' news :

The king of the martians wants to conduct a martian football tournament. There are n football teams participating in the tournament numbered form 1,2,...n. The martian sports analysts have rated the teams according to footballing ability and team i has been assigned integer rating a[i]. (a[i]'s might be negative.)

The tournament is conducted as follows : A permutation f of (1,2,...n) is taken as reference. All pairs of teams with team numbers adjacent in the permutation f play exactly one match in the tournament. More formally, (n-1) matches are played in the tournament and the ith match is played between teams f(i) and f(i+1).

The disparity of a match is the absolute difference in the ratings of the two teams playing the match. The disparity of the tournament is the sum of the disparities of all matches in the tournament.

The king of the martians likes to see routs more than close contests and is therefore interested in maximizing the disparity. The king wants to select a permutation f so as to maximize the total disparity of the tournament.

For this purpose he has asked freakin' news to find out the maximum possible disparity of the tournament given the number of teams and their ratings. Your job is to do this task for freakin' news.

[In case you were wondering who wins the tournament, the winner is the team which the queen thinks is the most adorable. That however, is irrelevant to your task.]

Input

The first line of input contains a single integer n. The next line consists of n space seperated integers a[1], a[2], ... a[n] : the team ratings.

Output

On the only line of output, output a single integer : the maximum possible disparity of the tournament.

Constraints

2<=n<=1000
|a[i]|<=100000

Sample Input 1:

2
6 -4

Sample Output 1:

10

Sample Input 2:

3
3 5 7

Sample Output 2:

6

Explanation:

1 : Absolute disparity of 10 can be obtained by the permutations (1,2) and (2,1).
2 : Absolute disparity of 6 can be obtained by the permutations (1,3,2), (2,1,3), (2,3,1) and (3,1,2).

Consider the permutation (2,1,3) in the second sample test case. The absolute disparity in this test case is | a[2]-a[1] | + | a[1]-a[3] | = |5-3| + |3-7| = 6

Author: architk
Date Added: 22-03-2012
Time Limit: 1 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, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

What does "internal error"

KADR @ 31 Mar 2012 06:52 PM
What does "internal error" verdict means?

I've made a resubmit and got

KADR @ 31 Mar 2012 06:57 PM
I've made a resubmit and got AC, but now I have 20 minutes of penalty. Please, rejudge my first submit.

Ok. Will contact Codechef

architk @ 31 Mar 2012 06:58 PM
Ok. Will contact Codechef about your first solution.

All solutions which were not

architk @ 31 Mar 2012 08:08 PM
All solutions which were not accepted (including internal errors) are being tested again.

again "internal error"

jzjsuper @ 31 Mar 2012 08:12 PM
again "internal error"

I had two accepted solutions

conankudo @ 31 Mar 2012 08:51 PM
I had two accepted solutions of IITI00 and IITI01, and both of them are internal errors now...?!

SUCCESSFUL SUBMISSIONS


Fetching successful submissions