Trapping Rain Water

Given an array of non-negative integers representing the height of buildings, your task is to compute the total amount of rainwater that can be trapped between these buildings after a rainfall. The water trapped at each position is determined by the formula:

\( water[i] = \min(left_{max}[i],\, right_{max}[i]) - height[i] \)

where \( left_{max}[i] \) is the maximum height to the left of index \( i \) (including \( i \)) and \( right_{max}[i] \) is the maximum height to the right of index \( i \) (including \( i \)).

Your program should read the input from standard input and print the result to standard output.

inputFormat

The first line contains a single integer ( n ), representing the number of buildings. The second line contains ( n ) space-separated integers, each representing the height of a building.

outputFormat

Output a single integer that represents the total units of water trapped after the rainfall.## sample

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

6