Trapping Rain Water

Given an array of non-negative integers representing the heights of bars, compute how much water can be trapped after a rain. At index \(i\), the water trapped is given by the formula \(w_i = \max(0, \min(L_i, R_i) - h_i)\), where \(L_i\) and \(R_i\) denote the maximum heights to the left and right of index \(i\), respectively. Solve the problem for multiple test cases.

inputFormat

The input is given via standard input. The first line contains an integer \(T\) representing the number of test cases. For each test case, the first line contains an integer \(N\) representing the number of bars, followed by a line with \(N\) space-separated integers denoting the heights of the bars.

outputFormat

For each test case, output a single integer on a new line indicating the total amount of water trapped.

1
6
0 1 0 2 1 0

1