Maximum Water Trapped

Given an array of non-negative integers representing the heights of buildings, your task is to compute the maximum amount of water that can be trapped between these buildings after it rains. The water trapped at position (i) is determined by the expression

[ water[i] = \min(left_max[i],\ right_max[i]) - height[i] ]

where (left_max[i]) is the maximum height to the left of position (i) (inclusive), and (right_max[i]) is the maximum height to the right of position (i) (inclusive). The total water trapped is the sum over all positions. Write a program to compute this value.

inputFormat

The first line contains an integer (n), which indicates the number of buildings. The second line contains (n) space-separated non-negative integers that represent the heights of the buildings.

outputFormat

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

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

6