Trapping Rainwater

You are given an array of non-negative integers representing the elevation map where the width of each bar is 1. Your task is to compute how much water it is able to trap after raining.

The water trapped at a given index is determined by the formula:

\(water = \min(\text{max}_{\text{left}}, \text{max}_{\text{right}}) - height[i]\)

where \(\text{max}_{\text{left}}\) is the highest bar on the left of the current bar and \(\text{max}_{\text{right}}\) is the highest bar on the right. If the computed value is negative, take it as zero.

You need to process multiple test cases. For each test case, compute and output the total trapped rainwater.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer \(T\) denoting the number of test cases. Each test case consists of two lines:

• The first line contains an integer \(N\) indicating the number of bars.
• The second line contains \(N\) space-separated non-negative integers representing the heights of the bars.

Constraints:

• \(1 \leq T \leq 10^4\)
• \(1 \leq N \leq 10^5\)
• \(0 \leq height[i] \leq 10^5\)

outputFormat

For each test case, output a single integer in a new line representing the total amount of trapped rainwater.

## sample

1
4
4 1 1 4

6

</p>