Trapping Rain Water

You are given an array representing an elevation map where the width of each bar is 1. Your task is to compute how much water can be trapped after raining. The water trapped at position \(i\) is determined by the minimum of the maximum heights to its left and right minus the current height. Formally, the water trapped at position \(i\) is given by:

$$water_i = \max\Big(0, \min(L_{max}(i), R_{max}(i)) - height_i\Big)$$

The total trapped water is the sum of \(water_i\) over all positions \(i\).

inputFormat

The input consists of two lines. The first line contains an integer \(n\) representing the number of elements in the elevation map. The second line contains \(n\) non-negative integers separated by spaces, each representing the height of a wall in the elevation map.

outputFormat

Output a single integer denoting the total amount of water that can be trapped after raining.

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

6