Trapping Rain Water

Given an array of non-negative integers representing the heights of buildings, compute the total volume of water that can be trapped after raining. The water trapped at any position is determined by the formula:

$$W(i) = \min(\max_{j \le i}(h_j), \max_{j \ge i}(h_j)) - h_i$$

where \(h_i\) is the height of the building at position \(i\). Your task is to calculate the sum of trapped water across all positions. The solution should run efficiently, even for large arrays.

inputFormat

The input is given via standard input (stdin) in the following format:

• The first line contains a single integer n (0 ≤ n ≤ 10⁵) representing the number of buildings.
• If n > 0, the second line contains n space-separated non-negative integers, each representing the height of a building.

outputFormat

Output a single integer to standard output (stdout), which is the total amount of water that can be trapped.

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

6