Maximum Rainwater Trapping

In this problem, you are given a sequence of non-negative integers that represent the heights of buildings. The task is to compute the maximum units of rainwater that can be trapped between these buildings after a rain.

For any building at index (i), the water that can be trapped above it is determined by the formula: [ \text{water}[i] = \max\Big(0, \min(\text{leftMax}[i],, \text{rightMax}[i]) - \text{height}[i]\Big), ] where (\text{leftMax}[i]) is the maximum height to the left of (i) (inclusive) and (\text{rightMax}[i]) is the maximum height to the right of (i) (inclusive).

Your program should read input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input begins with a single integer (n) ((n \ge 0)) representing the number of buildings. If (n > 0), the next line contains (n) space-separated non-negative integers representing the heights of the buildings.

outputFormat

Output a single integer which is the total amount of rainwater that can be trapped.## sample

6
3 0 0 2 0 4

10