Martian Football Tournament

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, (n1) 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]  = 53 + 37 = 6
Author:  architk 
Tags  architk 
Date Added:  22032012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, 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
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
What does "internal error"
I've made a resubmit and got
Ok. Will contact Codechef
All solutions which were not
again "internal error"
I had two accepted solutions