Trapping Rain Water

In this problem, you are given an array representing the heights of buildings. When it rains, water is trapped between these buildings. Your task is to compute the total amount of water that can be trapped.

The water trapped at a particular index is determined by the formula: [ water[i] = \max(0, \min(\text{max}{left}(i), \text{max}{right}(i)) - height[i]) ] where (\text{max}{left}(i)) is the maximum height to the left of index (i) and (\text{max}{right}(i)) is the maximum height to the right of index (i).

You need to read the input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The first line of input contains an integer (n) representing the number of buildings. If (n > 0), the second line contains (n) space-separated integers indicating the height of each building. If (n = 0), no further input is provided.

outputFormat

Output a single integer representing the total amount of trapped rain water.## sample

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

6