Trapping Rain Water

Given an array representing the heights of buildings, compute the total amount of water that can be trapped between them. The water trapped at a particular building is determined by the minimum of the maximum heights to its left and right, minus the height of the building at that position, i.e. ( water_i = \min(leftMax_i, rightMax_i) - height_i ). If the value is negative, consider it as zero water at that position. This problem requires you to implement an efficient solution that computes the answer in linear time.

inputFormat

The first line contains an integer (n) representing the number of buildings. The second line contains (n) space-separated integers, each denoting the height of a building.

outputFormat

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

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

6