Trapping Rain Water

Given an elevation map represented by an array of non-negative integers, compute the maximum amount of water that can be trapped after raining. The elevation map is provided as an array where each element represents the height of a building. The trapped water is calculated based on the elevations of the buildings to the left and right of each position.

The classic two-pointer technique can be used to solve this problem efficiently. The approach involves moving pointers from the beginning and end of the array toward the center, keeping track of the maximum height seen so far from both directions. The water that can be trapped at each position is determined by the difference between the current height and the minimum of the two maximum values.

This problem is often formulated using the following relation:

\( water = \sum_{i=0}^{n-1} \max(0, \min(\text{left_max}_i, \text{right_max}_i) - height[i]) \)

inputFormat

The first line of the input contains a non-negative integer n representing the number of elements in the elevation map. The second line contains n space-separated non-negative integers representing the heights of the buildings.

outputFormat

Output a single integer representing the maximum amount of water that can be trapped.

## sample

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

6

</p>