Trapping Rainwater Problem Statement

You are given an array ARR of long type, which represents an elevation map where ARR[i] denotes the elevation of the ith bar. Calculate the total amount of rainwater that can be trapped within these elevations.

Input:

The first line contains an integer 'T', denoting the number of test cases. Each test case consists of two lines. The first line contains an integer 'N', representing the size of the array. The second line contains 'N' single space-separated integers, representing the elevation of the bars.

Output:

For each test case, output a single integer in a new line, indicating the total water that can be trapped.

Example:

Input:

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

Output:

4
7

Constraints:

• 1 ≤ T ≤ 10
• 0 ≤ N ≤ 104
• 0 ≤ ARR[i] ≤ 109
• Time Limit: 1 sec

Note:

The width of each bar is uniform and equals 1.