Trapping Rain Water

Given an array of non-negative integers representing the heights of buildings, compute the total amount of water that can be trapped after a rainfall. The water level on each building is determined by the minimum of the maximum height to its left and right minus the height of the building itself.

The challenge is to implement an efficient algorithm with a time complexity of \( O(n) \). Please note that the input will be provided via standard input, where the first line contains an integer \( n \), followed by \( n \) space-separated integers representing the heights of the buildings.

inputFormat

The first line contains a single integer \( n \) — the number of buildings. The second line contains \( n \) space-separated non-negative integers, where each integer represents the height of a building.

outputFormat

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

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

6