Trapping Rain Water

Given an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given a sequence of non-negative integers where each integer represents the elevation of a point on the map. When it rains, water is trapped in the dips between the bars. The amount of water trapped at each index can be computed using the formula:

\( water[i] = \min( left\_max[i],\; right\_max[i] ) - elevation[i] \)

where \(left\_max[i]\) is the maximum height from the left up to index \(i\) and \(right\_max[i]\) is the maximum height from the right from index \(i\).

Your task is to read the elevation data from the standard input, compute the total water that can be trapped, and output the result to standard output.

inputFormat

The first line contains an integer \(n\), which is the number of elevation points. The second line contains \(n\) space-separated non-negative integers representing the elevation map.

outputFormat

Output a single integer, which is the total volume of water that can be trapped.

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

6