Trapping Rain Water

You are given an array of non-negative integers representing an elevation map where the width of each bar is 1. Compute how much water can be trapped after raining.

The water trapped at index i is determined by the formula:

\( \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 and \( \text{right\_max}[i] \) is the maximum height to the right of index i.

Read the input from standard input and output the total trapped water to standard output.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer n which is the number of blocks. If n is 0, then there are no blocks.
• The second line contains n space-separated non-negative integers representing the heights of the blocks.

outputFormat

Output to standard output (stdout) a single integer representing the total amount of water that can be trapped.

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

6