Trap Rain Water

You are given an array of non-negative integers representing the heights of buildings. When it rains, water is trapped between these buildings. Your task is to compute the total volume of water that can be trapped.

The water trapped at each position i is determined by the formula:

\( W[i] = \min(L[i], R[i]) - H[i] \)

where:

• \( H[i] \) is the height at position i,
• \( L[i] \) is the maximum height to the left of position i (including \( H[i] \)), and
• \( R[i] \) is the maximum height to the right of position i (including \( H[i] \)).

The overall trapped water is the sum \( \sum_{i=0}^{n-1} W[i] \), where each \( W[i] \) is taken as zero if the result is negative.

inputFormat

The first line of input contains one integer n (the number of buildings). The second line contains n space-separated non-negative integers representing the height of each building.

Constraints: \(1 \le n \le 10^4\) and \(0 \le H[i] \le 10^3\).

outputFormat

Output a single integer representing the total volume of water that can be trapped.

## sample

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

6