Trapping Rain Water

Given an array of non-negative integers representing the heights of buildings where the width of each building is 1, compute the total amount of rain water that can be trapped between the buildings after a heavy rain.

Mathematically, for each building at index i, the water that can be trapped is determined by:

\( w_i = \max(0, \min(\max_{0 \leq j \leq i} h_j, \max_{i \leq j \leq n-1} h_j) - h_i) \)

The final answer is the sum of water trapped at each index:

\( \text{Water Trapped} = \sum_{i=0}^{n-1} w_i \)

Please note that if there are less than 3 buildings, no water can be trapped.

inputFormat

The input is given via standard input (stdin) and consists of two lines. The first line contains an integer n denoting the number of buildings. The second line contains n space-separated non-negative integers representing the heights of the buildings. If n is 0, the second line may be empty.

outputFormat

Output a single integer representing the total amount of water that can be trapped.## sample

0

0