Trapping Rain Water

You are given an integer array representing the heights of buildings. Rainwater can be trapped between the buildings, and your task is to calculate the total amount of water that can be trapped after raining.

For each index i, the water trapped is determined by the formula:

\[ w_i = \max\Big( \min(L_i, R_i) - h_i,\ 0 \Big) \]

where:

• h_i is the height of the building at index i,
• L_i is the maximum height among all buildings to the left of index i,
• R_i is the maximum height among all buildings to the right of index i.

The total trapped water is the sum of \(w_i\) for all i.

inputFormat

The input is given from standard input in the following format:

n
h1 h2 ... hn

where:

• n is a non-negative integer representing the number of buildings. If n = 0, there will be no building heights on the next line.
• Each hi is a non-negative integer representing the height of the i^th building.

outputFormat

Output a single integer which is the maximum water that can be trapped, printed to standard output.

## sample

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

6