Trapping Rain Water

You are given an elevation map represented by a list of n non-negative integers where each integer represents the height of a bar and the width of each bar is 1. Your task is to compute how much water it is able to trap after raining.

The water trapped at any index is determined by the maximum height to its left and right. The water level at that index is the minimum of these two maximums, and the trapped water is the difference between this water level and the height of the bar, if positive.

Note: If there is no bar (empty list) or only one bar, no water will be trapped.

Mathematically, the water trapped at index i can be expressed in \( \text{water}[i] = \max(\min(\text{left\_max}[i],\,\text{right\_max}[i]) - \text{height}[i],\,0) \).

inputFormat

The first line of input contains a single integer n, representing the number of bars in the elevation map.

If n > 0, the second line contains n space-separated integers which represent the heights of the bars. If n = 0, there is no second line.

outputFormat

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

0

0