Trapping Rain Water

Given an array of non-negative integers representing the height of bars, compute how much water can be trapped after raining. The water trapped above a bar is determined by the minimum of the maximum bar height to its left and its right, minus the bar's own height.

Mathematically, for each index \(i\), the water trapped is given by:

$$w_i = \max\Big(0, \min(\text{left\_max}_i,\; \text{right\_max}_i) - height_i\Big)$$

Your task is to calculate the total amount of water that can be trapped. This is a classic problem often solved using dynamic programming or two-pointer techniques.

inputFormat

The first line of input 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, the total amount of rainwater that can be trapped.

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

6