Trapping Rain Water

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how many units of water can be trapped after raining. Intuitively, water is trapped between buildings. For each index i, the water trapped is given by the formula: $$ \min(\text{left\_max}_i,\; \text{right\_max}_i) - heights_i $$ where left_max[i] is the maximum height to the left of index i and right_max[i] is the maximum height to the right of index i. Your task is to implement a solution that reads the heights from standard input and outputs the total trapped water on standard output.

inputFormat

The input is given from stdin and has two lines:

• The first line contains an integer n (where n ≥ 0) representing the number of elements.
• The second line contains n non-negative integers separated by spaces denoting the elevation map.

If n is 0, the second line may be omitted.

outputFormat

Output a single integer on stdout representing the total units of water that can be trapped after raining.

4
0 1 0 2

1