## WOSS Dual Olympiad 2023 Team Round P2: Holding Eggnog

View as PDF

Points: 7
Time limit: 2.0s
Memory limit: 1G

Authors:
Problem type

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:

#### 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.