Jacob had a terrible nightmare! In his dream, a city with $N$ adjacent, $2$-dimensional buildings got flooded with eggnog! The $i$th building has a width of $1$ and a height of $h_i$. Calculate the maximum amount of eggnog the city can hold such that the eggnog is stable. This means that the eggnog must not move under the influence of gravity.

An example of a stable position is below:

Constraints

$1\le N\le {10}^5$

$1\le h_i\le {10}^9$

Input Specification

The first line contains a single integer $N$.

The second line contains $N$ space-separated integers $h_i$, the heights of the buildings.

Output Specification

Output a single integer, the capacity of the city.

Sample Input

8
6 2 3 1 8 4 5 7

Sample Output

17

Explanation for Sample

The input corresponds to the image in the example configuration.

The $2$nd building from the left has $4$ units of eggnog above it.

The $3$rd building has $3$ units above it.

The $4$th building has $5$ units.

The $6$th building has $3$ units.

The $7$th building has $2$ units.