Trapping Rain Water

You are given a sequence of non-negative integers representing the heights of buildings. When it rains, water will be trapped between these buildings. Your task is to determine the total amount of water that will be trapped.

The water trapped above a building at index i is determined by the formula:

[ w_i = \min(\text{leftMax}_i, \text{rightMax}_i) - h_i, ]

where:

• \( h_i \) is the height of the building at index \( i \),
• \( \text{leftMax}_i \) is the maximum height among the buildings to the left of index \( i \) (including \( i \) itself),
• \( \text{rightMax}_i \) is the maximum height among the buildings to the right of index \( i \) (including \( i \) itself).

The total water trapped is the sum of \( w_i \) for all indices \( i \). Note that if \( w_i \) is negative, it is treated as zero.

inputFormat

The input is read from stdin and contains two lines:

1. The first line contains an integer \( n \) representing the number of buildings.
2. The second line contains \( n \) space-separated integers representing the heights of the buildings.

outputFormat

Output a single integer to stdout representing the total amount of water trapped between the buildings.

## sample

6
0 1 0 2 1 0

1

</p>