#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
int a[100003], t=LLONG_MAX;
void dfs(int lpos, int rpos, char lr, int crt){
	if(rpos<lpos){
		t=min(t, crt);
		return;
	}
	if(lr=='l'){
		crt+=a[lpos], lpos++;
		for(int i=lpos; i<=rpos; ++i){
			if(a[i]<=a[i-1]) lpos++;
			else{
				a[i]-=a[i-1];
				break;
			}
		}
	}
	else{
		crt+=a[rpos], rpos--;
		for(int i=rpos; i>=lpos; --i){
			if(a[i]<=a[i+1]) rpos--;
			else{
				a[i]-=a[i+1];
				break;
			}
		}
	}
	dfs(lpos, rpos, 'l', crt);
	dfs(lpos, rpos, 'r', crt);
}
void ffff(){
	int n; cin>>n;
	for(int i=1; i<=n; ++i) cin>>a[i];
	t=LLONG_MAX;
	dfs(1, n, 'l', 0);
	dfs(1, n, 'r', 0);
	cout<<t<<'\n';
}
signed main(){
	int T; cin>>T;
	while(T--) ffff();
}

当时差这题就 AK 了求助 补下当时的遗憾