Trapping Rain Water

Given a list of non-negative integers representing the heights of blocks, your task is to compute how much water can be trapped between the blocks after it rains. The water trapped above each block is determined by the formula:

\( water_i = \min(left\_max_i,\, right\_max_i) - height_i \)

where \( left\_max_i \) is the maximum height to the left of the current block (including the block itself) and \( right\_max_i \) is the maximum height to the right. Sum these values for all blocks to get the total trapped water.

The solution should read input from stdin and output the result to stdout.

inputFormat

The first line contains an integer \( n \) representing the number of blocks. The second line contains \( n \) space-separated non-negative integers representing the heights of the blocks.

If \( n = 0 \), there will be no further input, and the answer is \( 0 \).

outputFormat

Output a single integer representing the total units of trapped water.

## sample

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

6

</p>