Trapping Rain Water

Given a list of non-negative integers representing the heights of blocks, determine how much water can be trapped after it rains. When rain water falls over the blocks, water will be trapped between the blocks if there is a taller block on both sides. Formally, for each index i, the water trapped above block i is given by

$$\text{water}_i = \max\left(0, \min\left(\max_{j\le i}(h_j),\; \max_{j\ge i}(h_j)\right) - h_i\right) $$

Your task is to compute the total amount of water trapped, which is equal to the sum over all indices:

$$\text{Total Water} = \sum_{i=0}^{n-1} \text{water}_i $$

Input is given via standard input where the first line contains an integer n specifying the number of blocks, and the second line contains n space-separated integers representing the height of each block.

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

inputFormat

The first line of input contains a single integer n (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 representing the total units of water that can be trapped.

## sample

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

6