Trapping Rain Water

You are given a list of non-negative integers representing the height of blocks.

The problem is to compute how much water it can trap after raining. The water trapped at index i can be calculated by the formula:

$\text{water}_i = \min(\text{left\_max}_i,\; \text{right\_max}_i) - \text{height}_i$

where:

• $\text{left\_max}_i$ is the maximum height to the left of index i (inclusive).
• $\text{right\_max}_i$ is the maximum height to the right of index i (inclusive).

Your task is to compute the total amount of water that can be trapped.

inputFormat

The first line of the input contains an integer n ($1 \leq n \leq 10^5$) representing the number of blocks.

The second line contains n space-separated non-negative integers representing the heights of the blocks.

outputFormat

Output a single integer, the maximum amount of water that can be trapped.

## sample

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

6