Trapping Rain Water

Given a sequence of non-negative integers representing the heights of bars, compute how much water it is able to trap after raining.

Imagine the histogram formed by these bars. The water trapped at each position is determined by the minimum of the maximum height to its left and right, minus its own height. If a bar is on the edge, it cannot trap water. Your task is to calculate the total units of water that can be trapped.

Note: If there are no bars, the trapped water will be 0.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains an integer n representing the number of bars.
• If n > 0, the second line contains n space-separated non-negative integers representing the heights of the bars.

outputFormat

The output, written to standard output (stdout), is a single integer representing the total units of trapped water.

12
0 1 0 2 1 0 1 3 2 1 2 1

6