Trapping Rain Water

Given an array heights of non-negative integers where each integer represents the height of a bar and the width of each bar is 1, compute how much water can be trapped after raining.

The water trapped at each index depends on the maximum height to the left and right of that index. Mathematically, for each index \(i\), if \(L_i\) is the maximum height to the left and \(R_i\) the maximum height to the right, the water trapped is \(\max(0, \min(L_i, R_i) - heights[i])\). The total trapped water is the sum for all indices.

inputFormat

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

outputFormat

Output a single integer representing the total amount of trapped rain water.

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

6