Trapping Rain Water

You are given an array of n non-negative integers representing the heights of bars in a histogram. Rainwater is trapped between the bars after it rains. Your task is to compute the total amount of water that can be trapped.

For each position i, the water that can be trapped is given by the formula:

$$ water(i) = \min(\text{leftMax}_i, \text{rightMax}_i) - heights[i] $$

where \( \text{leftMax}_i \) is the maximum height to the left of index \(i\) (including \(i\)), and \( \text{rightMax}_i \) is the maximum height to the right of index \(i\) (including \(i\)).

If no water can be trapped, output 0.

inputFormat

The first line contains an integer n, representing the number of bars. If n = 0, there is no second line. Otherwise, the second line contains n space-separated non-negative integers which represent the heights of the bars.

Example:

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

outputFormat

Output a single integer representing the total water trapped.

Example:

6

## sample

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

6