Trapping Rain Water

Given a list of non-negative integers representing the heights of bars (where each bar's width is 1), compute how much water is trapped after a rain.

The classic trapping rain water problem can be described mathematically. For an array of bar heights \(h[0], h[1], \dots, h[n-1]\), the water trapped at index \(i\) is given by:

\(\text{water}[i] = \min(\max_{j \leq i} h[j], \max_{j \geq i} h[j]) - h[i]\),

if this value is positive; otherwise, it is 0. The total water trapped is the sum of \(\text{water}[i]\) for all indices.

Input and Output: The input consists of two lines. The first line contains a single integer \(n\) (the number of bars). The second line contains \(n\) space-separated non-negative integers representing the heights of the bars. The output is a single integer representing the total amount of water trapped.

Example:

Input:
12
0 1 0 2 1 0 1 3 2 1 2 1
Output:
6

</p>

inputFormat

The first line of input contains an integer \(n\), representing the number of bars. The second line contains \(n\) space-separated non-negative integers, each indicating the height of a bar.

outputFormat

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

## sample

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

6