#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e7+10;
const int MAX=0x3f3f3f3f;
ll T,n,ans=MAX,a[MAXN];
ll tl[MAXN],tr[MAXN],l[MAXN],r[MAXN];
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++){
			tl[i]=tl[i-1];
			if(l[i-1]>=a[i]){
				l[i]=a[i];
			}else{
				l[i]=a[i]-l[i-1];
				tl[i]+=l[i];
			}
		}
		for(int i=n;i>=1;i--){
			tr[i]=tr[i+1];
			if(r[i+1]>=a[i]){
				r[i]=a[i];
			}else{
				r[i]=a[i]-r[i+1];
				tr[i]+=r[i];
			}
		}
		for(int i=1;i<=n;i++){
			ans=min(ans,tl[i-1]+tr[i+1]+max(0ll,a[i]-l[i-1]-r[i+1]));
		}
		cout<<ans<<endl;
		for(int i=1;i<=n;i++)tl[i]=tr[i]=l[i]=r[i]=0;
		ans=MAX;
	}
	return 0;
}