[naglowek]
IX OI 2001/2002
 
Railways
Byteasar the Travelling Salesman
Superknight
Island
Castle
Insulator
Parcel
Counting-Out Rhyme
Ski Resort
Protocols
Minuses
Skiers
Balance
B-Smooth Numbers
Brackets
Cipher
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994

Main page

Polish version
 
IX Olimpiada Informatyczna 2001/2002

Task: izo
Author: Zbigniew Czech
Insulator

II stage contest  

The company Insumax produces multilayer thermal insulators. Each of the i layers, i=1, 2, ..., n, of such an insulator is characterized by positive insulation coefficient ai. The layers are numbered according to the direction the heat leaks.

heat      ->      || a1 | a2 | ... | ai | ai+1 | ... | an ||      ->     

The insulation coefficient of the whole insulator, A, is described by the sum of insulation coefficients of its layers. Moreover, the coefficient A raises if a layer with a smaller insulation coefficient is followed by a layer with a larger coefficient, according to the formula:

insulation coefficient formula

For example, the insulation coefficient of the insulator of the form

->     || 5 | 4 | 1 | 7 ||      ->

is A = (5+4+1+7)+(7-1) = 23.

Task

Write a program which, for given insulation coefficients of layers a1, a2, ..., an, determines such an ordering of the layers that the insulation coefficient of the whole insulator is maximised.

Input

In the first line of the text file izo.in there is the number of layers n, 1 <= n <= 100000. In the successive n lines there are coefficients a1, a2, ..., an, one per line. Those coefficients are integers satisfying the inequalities 1 <= ai <= 10000.

Output

In the first and only line of the text file izo.out your program should write one integer equal to the largest possible value of the insulation coefficient A of the insulator built of the layers of the given coefficients, put in a particular order.

Example

For the following input file izo.in:
4
5
4
1
7
the correct answer is in the following output file izo.out:
24