Trapping Rain Water

You are given a sequence of non-negative integers where each integer represents the height of a building. When it rains, water can be trapped between the buildings. Your task is to compute the maximum volume of water that can be trapped after raining.

For each position i, the water that can be trapped is determined by:

$$w_i = \min( L_i, R_i ) - h_i$$

where:

• \(h_i\) is the height of the building at position i.
• \(L_i = \max_{0 \leq j \leq i} h_j\) is the maximum height on the left side of position i (inclusive).
• \(R_i = \max_{i \leq j < n} h_j\) is the maximum height on the right side of position i (inclusive).

The total trapped water is the sum of water trapped at each building. Note that if no water can be trapped, the output should be 0.

inputFormat

The input is provided via stdin in the following format:

n
h1 h2 h3 ... hn

Here, n is the number of buildings and h1, h2, ..., hn are the heights of the buildings separated by spaces. Note that n can be 0, in which case there are no building heights provided.

outputFormat

Output a single integer to stdout representing the maximum volume of trapped rain water.

## sample

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

6