Trapping Rain Water Problem

Given a histogram represented by a list of bar heights, compute the total amount of rain water that can be trapped after raining. The amount of water trapped at any position is determined by the equation ( water = \min(\text{left_max}, \text{right_max}) - h ), where (h) is the height at that position, and (\text{left_max}) and (\text{right_max}) are the maximum heights to the left and right of that position, respectively.

Your task is to implement a program that reads the input from standard input and writes the correct output to standard output.

inputFormat

The first line of input contains a single integer ( n ) (( n \geq 1 )), which is the number of bars in the histogram. The second line contains ( n ) space-separated non-negative integers representing the heights of the bars.

outputFormat

Output a single integer representing the total units of water that can be trapped.## sample

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

6