Trapping Rain Water

Given a sequence of non-negative integers representing the heights of buildings, your task is to compute the total amount of water that can be trapped between these buildings after it rains. The water trapped above each building is determined by the minimum of the maximum heights to its left and right, minus the height of the building itself. In mathematical terms, for each building at position \(i\), the water trapped is given by:

\(w_i = \max(0, \min(\text{left\_max}_i,\, \text{right\_max}_i) - A[i])\)

where \(A[i]\) is the height at position \(i\), \(\text{left\_max}_i\) is the maximum height among buildings on the left of \(i\), and \(\text{right\_max}_i\) is the maximum height among the buildings on the right of \(i\).

Your program should read the input from stdin and output the result to stdout.

inputFormat

The input starts with an integer (n) ((n \geq 1)) on the first line, representing the number of buildings. The second line contains (n) space-separated integers representing the height of each building.

outputFormat

Output a single integer on a line by itself, representing the total amount of trapped water.## sample

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

6