Trapping Rain Water

You are given an array of non-negative integers that represent the heights of buildings. When it rains, water is trapped between the buildings. Your task is to calculate the total amount of water that can be trapped.

For each building at index i with height \(h_i\), the amount of water above it is determined by the formula:

\[ water_i = \min(\max_{j \le i} h_j, \max_{j \ge i} h_j) - h_i, \]

where \(\max_{j \le i} h_j\) is the maximum height to the left of the building (including itself) and \(\max_{j \ge i} h_j\) is the maximum height to the right (including itself). Sum \(water_i\) for all indices \(i\) to obtain the total trapped water.

Note: If the calculated water above a building is negative, treat it as zero.

inputFormat

The first line of input contains an integer n representing the number of buildings. The second line contains n space-separated integers, where each integer represents the height of a building.

For example:

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

outputFormat

Output a single integer that represents the total amount of water trapped between the buildings after raining, printed on a new line.

## sample

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

6

</p>