Trapping Rain Water

You are given an array of non-negative integers representing the heights of buildings. Each building has a width of 1. After a rain, water may get trapped between these buildings. Your task is to compute how much water is trapped.

The water trapped above any building is determined by the minimum of the maximum height to its left and right minus its own height. Formally, for each index i, the trapped water is given by:

[ water[i] = \max(0, \min(\text{left}{!i},,\text{right}{!i}) - heights[i]) ]

where \(\text{left}_{\!i}\) is the maximum height among buildings from index 0 to \(i\), and \(\text{right}_{\!i}\) is the maximum among buildings from \(i\) to the last index. The answer is the sum of water trapped at all positions.

inputFormat

The input is given via standard input in the following format:

1. An integer n denoting the number of buildings.
2. A line containing n space-separated non-negative integers representing the heights of the buildings.

outputFormat

Output via standard output a single integer representing the total units of water that can be trapped.

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

6