Trapping Rain Water Problem Statement

You are given a long type array/list ARR of size N, representing an elevation map. The value ARR[i] denotes the elevation of the ith bar. Your task is to determine the total amount of rainwater that can be trapped between these elevations.

The width of each bar is equal to 1.

Input

The first line contains an integer T which denotes the number of test cases. Each test case follows:

The first line of each test case contains an integer N, representing the size of the array/list.
The second line contains N space-separated integers representing the elevation of the bars.

Output

For each test case, print a single line containing a single integer denoting the total water that can be trapped.
The output for each test case should be printed on a new line.

Example:

Input:

T = 2 N = 4 ARR = [4, 2, 0, 3] N = 5 ARR = [5, 0, 0, 2, 1]

Output:

3 6

Explanation:

In the first test case, water can be trapped between the bars: 4 units at 1^st index level 2 and 3 units at 2^st index level 3.
In the second test case, the total trapped water is 6 units.

Constraints:

• 1 <= T <= 10
• 0 <= N <= 10^4
• 0 <= ARR[i] <= 10^9

Time Limit: 1 second