Insulator

The company Insumax produces multi-layer thermal insulators. Each insulator consists of $n$ layers, and the $i$-th layer ($i = 1, 2, \dots, n$) is described by a positive integer insulation coefficient $a_i$. The layers are numbered along the direction in which heat leaks out.

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

The insulation coefficient $A$ of the whole insulator is the sum of the coefficients of its layers. In addition, whenever a layer is followed by a layer with a larger coefficient, $A$ grows by that difference. Formally,

$A = \sum_{i=1}^{n} a_i + \sum_{i=1}^{n-1} \max(0,\ a_{i+1} - a_i)$

For example, arranging the layers in the order $5, 4, 1, 7$ gives $A = (5 + 4 + 1 + 7) + (7 - 1) = 23$.

Given the coefficients $a_1, a_2, \dots, a_n$ of the layers, arrange them so that the total insulation coefficient $A$ is maximized, and output that maximum value.

The first line contains the number of layers $n$ ($1 \le n \le 100000$). Each of the next $n$ lines contains one coefficient $a_i$. Every coefficient is an integer satisfying $1 \le a_i \le 10000$.

Output a single integer: the largest possible value of the total insulation coefficient $A$ over all orderings of the layers.