Trapping Rain Water

Given an array of integers representing the height of buildings, calculate the total amount of water trapped after it rains. The water that can be trapped at any building is determined by the minimum of the maximum height of buildings to its left and right minus the height of the building itself.

Mathematically, for each building at index \(i\), the water trapped is given by:

\(\text{water}_i = \max(0, \min(\max_{j \le i} (height[j]), \max_{j \ge i} (height[j])) - height[i])\)

Your task is to compute the sum of \(\text{water}_i\) for all indices \(i\) in the given array.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) representing the number of buildings. The second line contains (n) space-separated integers representing the heights of the buildings. If (n = 0), there will be no second line.

outputFormat

Output a single integer on standard output (stdout) which represents the total amount of water that can be trapped.## sample

0

0