Rainwater Accumulation on an Uneven Roof

Turtle's roof is uneven due to the irregular arrangement of roof tiles. After a heavy rain, water accumulates in the cavities on the roof. The roof is composed of n tiles arranged in a row, each of width 1 and with an integer height. The roof can be visualized as a grid: each tile occupies consecutive cells from the bottom up according to its height.

After the rain, a grid cell will accumulate water if, when extending horizontally both to the left and to the right, one can eventually reach a cell occupied by a tile. In other words, water is trapped in a gap if it is bounded on both the left and right by higher (or equal) tile levels. The total amount of water is the sum of all such water-filled cells.

For example, if n = 5 and the roof tile heights are [4, 2, 3, 5, 1] then the accumulated water is 3 units.

Note: In some test cases, the sequence of tile heights is generated using the recurrence relation below. The first height R₁ is given in the input, and for each i > 1 the height is generated by

\( R_i = (R_{i-1} \times 6807 + 2831) \mod 201701 \)

However, for the purpose of input, the heights are provided as n space-separated integers.

inputFormat

The first line contains a single integer n which is the number of roof tiles.

The second line contains n space-separated integers representing the heights of the tiles. In some test cases the heights are generated by the recurrence: the first integer is R₁ (with \(0 \le R_1 < 201701\)), and for every i > 1, \( R_i = (R_{i-1} \times 6807 + 2831) \mod 201701 \). Regardless, the input provides n tile heights.

outputFormat

Output a single integer, which is the total number of grid cells that accumulate water on the roof after the rain.

sample

5
4 2 3 5 1

3