Trapping Rain Water

You are given an array of non-negative integers representing the heights of bars. Your task is to compute how much water can be trapped after raining. The water trapped above bar i is calculated by the formula: $$water_i = \min(left_max[i],, right_max[i]) - height[i]$$, where $$left_max[i]$$ is the maximum height to the left of index i (inclusive) and $$right_max[i]$$ is the maximum height to the right of index i (inclusive).

inputFormat

Input is provided via standard input. The first line contains a single integer n (n >= 0) indicating the number of bars. If n > 0, the second line contains n space-separated non-negative integers representing the heights of the bars.

outputFormat

Output a single integer to standard output representing the total amount of rain water that can be trapped.## sample

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

6