Trapping Rain Water Calculation

Given an array representing the elevation map where the width of each bar is 1, compute how much water is trapped after raining. The problem requires you to calculate the total amount of water that can be trapped between the bars when it rains. Using a dynamic programming or two-pointer strategy is recommended.

The solution involves precomputing the maximum height to the left and right for each bar, and then using the formula \(\min(\text{left_max}[i], \text{right_max}[i]) - \text{height}[i]\) to determine the water above each bar. Your program should be efficient enough to handle multiple test cases.

inputFormat

The first line contains a single integer \(T\), representing the number of test cases. For each test case, the first line contains an integer \(n\), the number of bars. The second line contains \(n\) space-separated non-negative integers representing the height of each building.

outputFormat

For each test case, output a single integer that represents the total amount of trapped rain water. Each answer should be printed on a new line.

4
6
0 1 0 2 1 0
5
3 0 2 0 4
3
1 0 1
6
4 2 0 3 2 5

1
7
1
9