Trapping Rain Water

Given a list of non-negative integers representing the heights of buildings, compute how much water is trapped after raining. Consider that water will be trapped between the buildings if there is a taller building on both the left and right sides. The water trapped at a position i is given by:

\(w_i = \min(\max_{j\leq i} h_j,\, \max_{j\geq i} h_j) - h_i\)

where \(h_i\) is the height of the building at position \(i\). Sum up \(w_i\) for all indices to obtain the total water trapped.

inputFormat

The input is given via standard input (stdin) and consists of two lines.

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

outputFormat

Output a single integer representing the total amount of water that can be trapped between the buildings, printed via standard output (stdout).

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

6