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 can trap after raining.

The water trapped above each bar can be determined by the formula: \(water_i = \min(\max_{j \leq i} h_j, \max_{j \geq i} h_j) - h_i\), where \(h_i\) is the height at position \(i\).

inputFormat

The first line contains an integer \(n\), representing the number of bars in the elevation map. The second line contains \(n\) space-separated non-negative integers denoting the height of each bar.

outputFormat

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

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

6