Trapping Rain Water

You are given n non-negative integers representing the height of buildings. The width of each building is 1 unit. Your task is to compute how much water can be trapped after raining between these buildings.

Mathematically, if the array of heights is \( H = [h_1, h_2, ..., h_n] \), then the water that can be trapped at index \( i \) is given by:

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

If the result is negative, consider it as 0. The overall trapped water is the sum of water(i) for all valid indices.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer n representing the number of buildings. The second line contains n space-separated non-negative integers representing the height of each building.

outputFormat

Output a single integer on standard output (stdout) which is the total volume of water that can be trapped after raining.## sample

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

6