Description

A sequence of positive integers represents the heights of columns formed by stacking cubes. If a height value is $x$, it means $x$ unit cubes are stacked (as in the figure, $0 \le x \le 5000$). Find all positions where water can be trapped (the blue parts in the figure) and compute the total trapped area (this is the cross-sectional area in the figure. Each unit cube position corresponds to 1 unit area).

Example: the column heights change as 0 1 0 2 1 2 0 0 2 0.

The blue parts in the figure are the trapped area, totaling $6$ unit areas.

Input Format

Two lines. The first line contains $n$, the number of values ($3 \le n \le 10000$). The second line contains $n$ consecutive integers giving the heights of the stacked cubes in order, with the guarantee that the first and last values are $0$.

Output Format

A single number: the total trapped area.

10
0 1 0 2 1 2 0 0 2 0

6

Hint

Translated by ChatGPT 5