Trapping Rain Water

Given n bars where the width of each bar is 1, compute how much water it is able to trap after raining. The amount of water trapped above a bar at index i can be computed by the formula

where $$L_i$$ is the maximum height to the left of index i and $$R_i$$ is the maximum height to the right of index i. Your task is to calculate the total trapped water given the heights of the bars.

Note: Input is taken from standard input and output is printed to standard output.

inputFormat

The first line contains an integer n, representing the number of bars. If n is greater than 0, the second line contains n space-separated integers where each integer represents the height of a bar.

outputFormat

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

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

6