Trapped Rain Water

Given an array of non-negative integers representing the elevation map where the width of each bar is 1, compute how much water it can trap after raining. The amount of water trapped above a bar at index \(i\) is determined by the formula: \(water(i)=\min(max_{left}(i),\; max_{right}(i)) - height(i)\), where \(max_{left}(i)\) and \(max_{right}(i)\) are the maximum heights to the left and right of index \(i\), respectively. The goal is to sum the water trapped over all indices.

inputFormat

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

outputFormat

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

5
3 0 2 0 4

7