#include<bits/stdc++.h>
using namespace std;
long long t,n,a[100005]; 
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		int p=0,s=0;
		for(int l=1,r=n;l+1<=r;)
		{
			p=max(a[l],a[r]);
			s+=p;
			if(a[l]>a[r])
			{
				l++;
				while(p>=a[l]&&l<n)
				{
					p=a[l];
					l++;
				}
				a[l]-=p;
			}
			else
			{
				r--;
				while(p>=a[r]&&r>1)
				{
					p=a[r];
					r--;
				}
				a[r]-=p;
			}
		}
		cout<<s<<endl;
	}
	return 0;
}