#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n;
long long a[N],x[N],y[N],l[N],r[N];
int main(){
	cin>>t;
	while(t--){
		long long ans=LONG_LONG_MAX;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			x[i]=y[i]=a[i];
		}
		for(int i=1;i<=n;i++)
			if(x[i]>x[i-1]){
				x[i]-=x[i-1];
				l[i]=l[i-1]+x[i];
			}
			else
				l[i]=l[i-1];
		for(int i=n;i;i--)
			if(y[i]>y[i+1]){
				y[i]-=y[i+1];
				r[i]=r[i+1]+y[i]; 
			}
			else
				r[i]=r[i+1];
		for(int i=1;i<=n;i++)
			if(x[i-1]+y[i+1]<a[i])
				ans=min(ans,l[i-1]+r[i+1]+a[i]-x[i-1]-y[i+1]);
			else
				ans=min(ans,l[i-1]+r[i+1]);
		cout<<ans<<endl; 
	}
	return 0;
}