Trapping Rain Water

You are given a list of non-negative integers which represent the heights of vertical poles. The task is to compute how much water can be trapped between these poles after raining.

Imagine that the poles are placed adjacent to each other with unit width. Water will accumulate in the valleys between poles if they are bounded by taller poles on both sides. The water level on top of a pole is determined by the minimum of the maximum heights to its left and right minus the height of the pole itself.

The formula in latex is: \(\text{water} = \min(\max_{left}(i), \max_{right}(i)) - \text{height}(i)\) for each index \(i\), summing over all indices gives the total trapped water.

Your solution must parse the input from stdin and print the result to stdout.

inputFormat

The first line contains an integer \(n\), representing the number of poles. If \(n = 0\), it means the list is empty.

The second line contains \(n\) space-separated non-negative integers, each representing the height of a pole.

For example: 6\n0 1 0 2 1 0

outputFormat

Output a single integer representing the total amount of water that can be trapped between the poles.

For instance, for the input above, the output should be 1.

## sample

6
0 1 0 2 1 0

1