Trapping Rain Water

Given an elevation map represented by an array of non-negative integers, where each integer represents the height of a building and each building has a width of 1, compute how much water can be trapped after a heavy rain.

At index \(i\), the water that can be trapped is determined by \(\min(L_i, R_i) - h_i\), where \(L_i\) is the maximum height to the left of index \(i\), \(R_i\) is the maximum height to the right of index \(i\), and \(h_i\) is the height at index \(i\). If this value is negative, consider it as 0.

Your task is to calculate the total amount of trapped water.

inputFormat

The input is given via stdin and consists of two lines:

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

If \(n = 0\), it implies an empty elevation map and the trapped water is 0.

outputFormat

Output a single integer through stdout that represents the total amount of water trapped.

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

6