Trapping Rain Water

You are given an array of non-negative integers representing the heights of histogram bars. Compute how much water can be trapped between the bars after raining.

The water trapped above a bar is determined by the minimum of the maximum heights to its left and right, minus the height of the bar itself, mathematically formulated as:

\( water[i] = \max(0, \min(\text{leftMax}_{i}, \text{rightMax}_{i}) - height[i]) \)

Your task is to calculate the total amount of trapped water.

inputFormat

The input is given in two lines:

• The first line contains an integer \( n \) representing the number of bars.
• The second line contains \( n \) space-separated integers representing the heights of the bars.

outputFormat

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

## sample

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

6

</p>