Trapping Rain Water

You are given an array of non-negative integers height where each element represents the height of a block. Consider that rain falls on these blocks, and water is trapped between them. Your task is to calculate how much water can be trapped after raining.

The water trapped at any index is determined by the formula:

\( water_i = \min(\max_{j \leq i}height[j], \max_{j \geq i}height[j]) - height[i] \)

where \( height[i] \) is the height of the current block, \( \max_{j \leq i}height[j] \) is the maximum height to the left of the current block (including itself), and \( \max_{j \geq i}height[j] \) is the maximum height to the right of the current block (including itself). The answer is the sum of water trapped at each index.

Note that if no water is trapped, the answer should be 0.

inputFormat

The first line of input contains an integer n representing the number of blocks. The second line contains n space-separated non-negative integers which represent the heights of the blocks.

If n is 0, an empty list of blocks is assumed.

outputFormat

Output a single integer representing the total amount of water that can be trapped after raining.

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

6