Trapping Rain Water

Given a list of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water can be trapped after raining.

The water above a building at index \(i\) is determined by the formula:

\(water_i = \min(\text{left}_{max}, \text{right}_{max}) - height[i]\),

where \(\text{left}_{max}\) is the maximum height to the left (including the current building) and \(\text{right}_{max}\) is the maximum height to the right (including the current building). Your task is to calculate the total amount of water that can be trapped.

inputFormat

The first line contains an integer \(n\) representing the number of buildings. The second line contains \(n\) space-separated non-negative integers, where each integer represents the height of a building.

outputFormat

Output a single integer which is the total amount of water trapped.

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

6