#include<bits/stdc++.h>
using namespace std;

#define left l
#define right r
const int N = 1000010;
int n,a[N],left[N],right[N],w[N],T;
long long rec,cnt,cut;

int main(){
	cin >>T;
    while(T--){
        cin >> n;
    	rec = 0, cnt = 0, cut = 0;
    	for(int i = 1; i <= n; i++){
    		scanf("%d",&a[i]);
    	}
    	int maxn = a[1];
    	left[1] = 1;
    
    	for(int i = 2; i <= n; i++){
    		left[i] = maxn;
    		if(a[i] > maxn) maxn = a[i];
    	}
    	right[n] = 1;	
    	maxn = a[n];
    	for(int i = n-1; i >= 1; i--){
    		right[i] = maxn;
    		if(a[i] > maxn) maxn = a[i];
    	}
    	//记录初始积水量
    	for(int i = 1; i <= n; i++){
    		if(left[i] <= a[i] || right[i] <= a[i]){
                w[i] = 0;
                continue;
            }
    		else{
    			w[i] = min(left[i],right[i]) - a[i];
    			rec = rec + w[i];
    			
    		}
    	}

    	for(int i = 1; i <= n; i++){
    		if(left[i] > a[i] && right[i] > a[i]){
    			cnt = w[i];
    			if(cnt > cut) cut = cnt;
    		}
    	}

    	int i;
    	for(i = 1; i <= n;){
    		if(left[i] < a[i]){//开始下降 
    			int low = left[i];
    			int id = i;
                id++;
    			cnt = 0;
    			while(a[id] <= a[i] && id <= n){
    				if(low != left[id]){//change cnt
    					long long nowid;
    					if(low <= a[id] || right[id] <= a[id]) nowid = 0;
    					else{
    						nowid = max(0,(min(low,right[id]) - a[id]));
    					}
    					cnt = cnt + w[id] - nowid;
    				}
    				if(a[id] > low) low = a[id];
    				id++;		
    			}
    			i = id;
    			if(cnt > cut) cut = cnt;
    		}
    		else{
    			i++;
    		}
    	}
    	for(i = n; i >= 1;){
    		if(right[i] <= a[i]){//开始下降 
    			int low = right[i];
    			int id = --i;
    			cnt = 0;
    			while(a[id] < a[i] && id >= 1){
    				if(low != right[id]){//change cnt
    					long long nowid;
    					if(low <= a[id] || left[id] <= a[id]) nowid = 0;
    					else{
    						nowid = max(0,(min(low,left[id]) - a[id]));
    					}
    						cnt = cnt + w[id] - nowid;
    				}
    				if(a[id] > low) low = a[id];
    				id--;		
    			}
    			i = id;
    			if(cnt > cut) cut = cnt;
    		}
    		else{
    			i--;
    		}
    	}
    	cout << rec - cut << endl;
        for(int i = 0; i <= n + 1; i++){
            a[i] = 0;
        }
    }
    
	return 0;
}