Trapping Rain Water

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For each position i, the water that can be trapped is calculated as:

$$ \text{water}_i = \min(\text{left\_max}_i, \text{right\_max}_i) - H_i $$

where \( H_i \) is the height at position i, \( \text{left\_max}_i \) is the maximum height to the left of i (including i), and \( \text{right\_max}_i \) is the maximum height to the right of i (including i). The answer is the sum of water trapped over all indices. This is a classic problem often known as "Trapping Rain Water".

inputFormat

The first line contains a single integer n representing the number of bars. The second line contains n space-separated non-negative integers representing the heights of the bars.

outputFormat

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

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

6