Trap Rainwater

Given a list of non-negative integers representing the heights of blocks, determine how much water can be trapped after raining. The water trapped above block i is computed as (w_i = \min(\text{left}{i}, \text{right}{i}) - \text{height}i), where (\text{left}{i}) is the maximum height to the left of the block (including itself) and (\text{right}_{i}) is the maximum height to the right of the block (including itself). Your task is to compute the total water trapped. This problem is a classic challenge that often uses a two-pointer or dynamic programming approach.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (n) representing the number of blocks. The second line contains (n) space-separated non-negative integers representing the heights of the blocks.

outputFormat

Output the total volume of water trapped as an integer to standard output (stdout).## sample

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

6