Jacob had a terrible nightmare! In his dream, a city with adjacent, -dimensional buildings got flooded with eggnog! The th building has a width of and a height of . 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

#### Input Specification

The first line contains a single integer .

The second line contains space-separated integers , 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 nd building from the left has units of eggnog above it.

The rd building has units above it.

The th building has units.

The th building has units.

The th building has units.

## Comments