#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long a[N];
int main(){
	int t;
	cin>>t;
	for(int o=1;o<=t;o++){
		memset(a,0,sizeof a);
		int n;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		int l=1,r=n,sum=0,p=0;
		while(l<r){
			if(a[l]>a[r]){
				sum+=a[l];
				while(l!=r&&a[l]>=a[l+1]){
					l++;
				}
				if(a[l]<a[l+1]&&l+1<=n){
					a[l]-=a[l+1];
					l++;
				}
			}
			else if(a[l]<a[r]){
				sum+=a[r];
				while(l!=r&&a[r-1]<=a[r]){
					r--;
				}
				if(a[r-1]>a[r]&&r-1>=1){
					a[r-1]-=a[r];
					r--;
				}
			}
			else{
				int l1=l,r1=r,cnt1=0,cnt2=0;
				p=a[l];
				sum+=a[l];
				while(l1!=r1&&a[l1]>=a[l1+1]){
					l1++;
					cnt1++;
				}
				int l2=l1+1;
				l1=l;
				while(l1!=r1&&a[r1-1]<=a[r1]){
					r1--;
					cnt2++;
				}
				int r2=r1-1;
				if(cnt1>cnt2){
					l=l2;
					a[l2]-=p;
				}
				if(cnt1<=cnt2){
					r=r2;
					a[r2]-=p;
				}
			}
		}
		cout<<sum<<"\n"; 
	}
	return 0;
} 

纯贪心加模拟写的，样例包过但是爆0了，有大佬帮忙康康嘛