Trapping Rain Water Problem

Given a list of non-negative integers representing the heights of buildings, your task is to determine how much water can be trapped after it rains. The amount of water trapped at any position i is determined by the height of the tallest building to its left and right. Formally, the water trapped at position i is:

$\text{water}_i = \max(0, \min(\text{max}_{left}(i),\, \text{max}_{right}(i)) - height[i])$

where $\text{max}_{left}(i)$ is the maximum height from index 0 to i, and $\text{max}_{right}(i)$ is the maximum height from index i to the end of the array.

Your solution should read the height array from standard input and output the total amount of trapped water to standard output.

inputFormat

The input consists of two lines:

• The first line contains an integer n representing the number of buildings.
• The second line contains n space-separated integers representing the heights of the buildings. If n is 0, the second line may be omitted.

outputFormat

Output a single integer: the total amount of water that can be trapped.

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

6