Trapping Rain Water

Given a list of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The water trapped at index i is determined by the formula \(\text{water}[i] = \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 (inclusive) and \(\text{right\_max}[i]\) is the maximum height to the right of index i (inclusive). Your program should read the input from stdin and output the result to stdout.

inputFormat

The first line contains a single integer \(n\) (\(0 \leq n \leq 10^5\)), representing the number of bars in the elevation map. If \(n > 0\), the second line contains \(n\) non-negative integers separated by spaces, representing the height of each bar.

outputFormat

Output a single integer that represents the total amount of water that can be trapped.

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

6