Trapping Rain Water

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

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

\( \text{water}[i] = \max(0, \min(\text{max}_{left}[i], \text{max}_{right}[i]) - \text{height}[i]) \)

where \(\text{max}_{left}[i]\) is the maximum height to the left of index \(i\) (inclusive) and \(\text{max}_{right}[i]\) is the maximum height to the right of index \(i\) (inclusive). The total trapped water is the sum over all indices.

For example, given the elevation map [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the trapped water is 6.

inputFormat

The input is given via standard input.

The first line contains an integer \(n\) indicating the number of elements in the elevation map. The second line contains \(n\) space-separated non-negative integers representing the elevation heights.

outputFormat

Output a single integer representing the total volume of trapped water.

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

6