WOSS Dual Olympiad 2023 Team Round P2: Holding Eggnog

View as PDF

Submit solution

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

Problem type

Jacob had a terrible nightmare! In his dream, a city with N adjacent, 2-dimensional buildings got flooded with eggnog! The ith 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:


1 \leq N \leq 10^5

1 \leq h_i \leq 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

6 2 3 1 8 4 5 7

Sample Output


Explanation for Sample

The input corresponds to the image in the example configuration.

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

The 3rd building has 3 units above it.

The 4th building has 5 units.

The 6th building has 3 units.

The 7th building has 2 units.


There are no comments at the moment.