Trapping Rain Water

Given a list of non-negative integers representing an elevation map, where each integer corresponds to the height of a bar and each bar has a width of 1, your task is to compute how much water is trapped after it rains. The water trapped at a position is determined by the minimum of the maximum heights to the left and right minus the height at that position, mathematically represented as:

[ \text{water}_i = \max(0, \min(\text{maxLeft}_i, \text{maxRight}_i) - h_i) ]

An optimal solution uses a two-pointer technique to achieve O(n) time complexity. Your solution should read input from stdin and write the answer to stdout.

inputFormat

The input consists of two lines. The first line contains an integer (n) representing the number of bars. The second line contains (n) space-separated non-negative integers representing the elevation map.

outputFormat

Output a single integer which is the total amount of water that can be trapped.## sample

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

6