Trapping Rain Water

You are given a list of non-negative integers that represent an elevation map where the width of each bar is 1. Your task is to calculate how much water can be trapped between the buildings after it rains.

The water trapped at position \( i \) can be computed by the formula: \( w_i = \min(l_i, r_i) - h_i \), where:

• \( h_i \) is the height at position \( i \).
• \( l_i = \max_{0 \le j \le i}(h_j) \) is the maximum height to the left of \( i \) (inclusive).
• \( r_i = \max_{i \le j < n}(h_j) \) is the maximum height to the right of \( i \) (inclusive).

The total amount of water trapped is the sum of \( w_i \) for all indices \( i \). It is possible that for some indices, no water is trapped (i.e., \( w_i \le 0 \)).

inputFormat

Input is taken from stdin with the following format:

1. The first line contains an integer \( n \) that represents the number of buildings.
2. If \( n > 0 \), the second line contains \( n \) space-separated non-negative integers representing the heights of the buildings. If \( n = 0 \), there is no second line.

outputFormat

Output a single integer to stdout representing the total units of water trapped between the buildings.

6
0 1 0 2 1 0

1