Trapping Rain Water

Given an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

You are provided with a list of non-negative integers that represent the elevation of bars. The water that can be trapped at a given index i is determined by the formula:

$$water[i] = \min( L[i], R[i] ) - height[i]$$

where:

• $$L[i]$$ is the maximum height to the left of index i (including i).
• $$R[i]$$ is the maximum height to the right of index i (including i).

Your task is to find the total amount of trapped rainwater.

inputFormat

The first line of input contains a single integer n, representing the number of elements in the elevation map.

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

outputFormat

Output a single integer which is the total amount of trapped rainwater.

## sample

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

6