#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>T read(){
	T x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int a[100010],s[100010],s2[100010];
signed main(){
	int t=read<int>();
	while(t--){
		memset(s,0,sizeof(s));
		memset(s2,0,sizeof(s2));
		int n=read<int>(),ans=1e18;
		for(int i=1;i<=n;i++){
			a[i]=read<int>();
		}
		s[1]=a[1];
		int b[100010]={},c[100010]={};
		memcpy(b,a,sizeof(a));
		memcpy(c,a,sizeof(a));
		for(int i=2;i<=n;i++){
			if(a[i]>a[i-1]){
				s[i]=s[i-1]+a[i]-a[i-1];
				a[i]-=a[i-1];
			}
			else s[i]=s[i-1];
		}
		s2[n]=b[n];
		for(int i=n-1;i>=1;i--){
			if(b[i]>b[i+1]){
				s2[i]=s2[i+1]+b[i]-b[i+1];
				b[i]-=b[i+1];
			}
			else s2[i]=s2[i+1];
		}
		for(int i=1;i<=n;i++){
			int tmp=s[i-1]+s2[i+1]+max(c[i]-a[i-1]-b[i+1],0ll);
			ans=min(ans,tmp);
		}
		cout<<ans<<endl;
	}
	return 0;
}