Trapping Rain Water

Given an array representing an elevation map where each element corresponds to the height of a building (with a width of 1 unit), determine the total amount of rainwater that can be trapped after raining.

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

\(W_i = \min(left_i,\, right_i) - height_i\)

where \(left_i\) is the maximum height to the left of index \(i\) and \(right_i\) is the maximum height to the right of index \(i\). Note that if the computed value is negative, it is considered as 0 trapped water for that position.

inputFormat

The first line contains a single integer \(n\), the number of buildings.

The second line contains \(n\) space-separated non-negative integers representing the height of each building.

outputFormat

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

5
3 0 2 0 4

7