Trapping Rain Water

Given an array of non-negative integers representing the elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

In this problem, you are given a sequence of building heights. You need to calculate the total volume of water (in units) that can be trapped between these buildings after rainfall. The mathematical formulation can be described as follows:

For each index i, let \(L_i\) be the maximum height to the left of \(i\) (inclusive) and \(R_i\) be the maximum height to the right of \(i\) (inclusive). The water trapped at index i is given by \(W_i = \min(L_i, R_i) - h_i\), where \(h_i\) is the height at index i. The answer is \(\sum_{i} W_i\).

Your solution should read from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (with \(n \ge 0\)), representing the number of buildings.
• The second line contains \(n\) space-separated non-negative integers representing the heights of the buildings. If \(n = 0\), the second line may be omitted.

outputFormat

Output a single integer: the total trapped rain water.

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

6