The uneven ground always accumulates water when it rains. Assuming that the ground is one -dimensional, each width is 1, and the height is non -negative. Then you can use an array to express a piece of ground. For example, [0,1,0,2,1,1,1,3,2,1,2,1] can be used to indicate the floor of the figure below:

After the rain is over rain, the ground will accumulate water. The blue area in the picture above is the water accumulation area. Now give you an array to represent the ground, and how much water has the water accumulation of the ground after the rain (assuming that it does not evaporate and does not penetrate).

Input

The first line is an integer M, which means that there is a group M test sample, not more than 100.
The next M block, each line is a positive integer n, indicating the total width of the ground (array length), no more than 20,000.
The next line is N integer, which is separated by spaces, indicating the height of the ground.

Output

For the input of each group, an integer represents the water accumulation.

Sample Input

2
12
0 1 0 2 1 0 1 3 2 1 2 1
4
1 0 0 2

Sample Output

6
2

shortcoming effect

The amount of water depends on the height of the lower ground.

As shown in the figure, find the highest ground height on the left side of each column and the highest ground height on the right, find the minimum value of the two highest heights, and use the minimum value to minimize the current calculation column. The ground height, if the result is assigned after the decrease is reduced, the amount of water accumulation is not added, otherwise, add.

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[20010];
int left[20010],right[20010];
int main()
{
    
    int t;
    scanf("%d",&t);
    while(t--)
    {
    
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        int max1=0;
        for(int i=0; i<n; i++)// Seek the largest on the left
        {
    
            left[i]=max1;
            if(a[i]>max1)
                max1=a[i];
        }
        int max2=0;
        for(int i=n-1; i>=0; i--)// Zi U is the largest on the right
        {
    
            right[i]=max2;
            if(a[i]>max2)
                max2=a[i];
        }
        int sum=0;
        for(int i=0; i<n; i++)
        {
    
            int x=min(right[i],left[i]);// Seek the minimum value on both sides
            if(x-a[i]>0)
                sum+=(x-a[i]);
        }
        printf("%d\n",sum);
    }
    return 0;
}