Trapping Rain Water

Given a list of non-negative integers representing the heights of buildings arranged in a line, your task is to compute the total amount of rain water that can be trapped after it rains. The water trapped at each index i can be calculated using the formula:

$$ water[i] = \min(left_{max}[i],\, right_{max}[i]) - height[i] $$

where:

• left_max[i] is the maximum height of a building to the left of index i,
• right_max[i] is the maximum height of a building to the right of index i.

Your program should read input from standard input (stdin) and output the total trapped water on standard output (stdout).

inputFormat

The input is given via standard input and consists of two lines:

1. The first line contains a single integer n representing the number of buildings.
2. The second line contains n non-negative integers separated by spaces representing the heights of the buildings. If n = 0, the second line will be empty.

outputFormat

The output should be a single integer written to standard output, indicating the total amount of trapped rain water.

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

6