Trapped Rain Water

You are given an array of non-negative integers representing the heights of buildings. After a heavy rain, water may be trapped between the buildings. Your task is to calculate the total amount of water that can be trapped between these buildings.

The amount of water trapped above a building at position \(i\) can be computed 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 \(i\) (including itself), and \(right\_max[i]\) is the maximum height to the right of \(i\) (including itself). Sum the water trapped at each position to get the total trapped water.

Note: If there are fewer than 3 buildings, no water can be trapped.

inputFormat

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.

Example:

6
3 0 0 2 0 4

outputFormat

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

Example:

10

## sample

6
3 0 0 2 0 4

10

</p>