#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[100005],b[100005],ans1[100005],ans2[100005],c[100005],d[100005];
signed main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			b[i]=a[i];
		}
		int last=a[1];
		for(int i=1;i<=n;i++){
			ans1[i]=ans1[i-1]+a[i];
			c[i]=a[i];
			int pre=a[i+1]-last;
			last=a[i+1];
			a[i+1]=max(0ll,pre);
		}
		for(int i=1;i<=n;i++){
			a[i]=b[i];
		}
		for(int i=n;i>=1;i--){
			ans2[i]=ans2[i+1]+a[i];
			d[i]=a[i];
			int pre=a[i-1]-last;
			last=a[i-1];
			a[i-1]=max(0ll,pre);
		}
		int minn=min(ans1[n],ans2[1]);
		for(int i=2;i<n;i++){
			minn=min(minn,ans1[i-1]+ans2[i+1]+min(max(0ll,c[i]-c[i-1]),max(0ll,d[i]-d[i+1])));
		}
		cout<<minn<<"\n";
	}
	return 0;
}