News About Olympic History of OI OI books National team Olympic camps Photo gallery Links SIO MAIN
 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:

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

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

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

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
```

Print friendly version