Trapping Rain Water

You are given an array representing the heights of buildings. When it rains, water gets trapped between these buildings. Your task is to compute the total amount of water that is trapped.

For each index i, consider the maximum height to the left and right of i. The water above building i can be computed as:

\( \text{water}_i = \max(\min(\text{left\_max}_i, \text{right\_max}_i) - \text{height}_i,\ 0) \)

Your program should read the heights from standard input and output the total units of trapped water to standard output.

inputFormat

The first line contains a single integer n, the number of buildings. If n > 0, the second line contains n space-separated integers representing the heights of the buildings.

outputFormat

Output a single integer representing the total units of water that is trapped.

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

6