#include<iostream>
using namespace std;
int  biggest(int &start,int &end,int a[])
{
	int j,b,endb,startb,max,c=start,d=end;
	    endb=end;
		startb=start;
	     for(j=c+1;j<=d;j++)
		 {
			 if(b+a[j]>0)
			 {   
				b+=a[j];
				endb=j;					
			 }
			 else
			 {
			     startb=endb=j+1;
				 b=0;
			 }
			 if(b>max)
			 {  
				 start=startb;
				 end=endb;
				 max=b;
			 }
		 }
		 cout<<a[start]<<' '<<a[end]<<endl;
		 return max;
}

int main()
{
	int T,n,a[50001],i,j,top,max,b,start,end,num,newstart,newend,num0,num1,num2,nn;
	cin>>T;
	for(i=0;i<T;i++)
	{
		cin>>n;
		for(j=1;j<=n;j++)
			cin>>a[j];
         max=a[1];
		 b=max;
		 top=0;
	
		
		 start=1;
		 end=n;	
		 num=biggest(start,end,a);
		
		 newend=start-1;
		 newstart=end;
		 j=0;
		 nn=n;
         num0=biggest(j,newend,a);
		 num1=biggest(newstart,nn,a);
		 num2=num0>num1?num0:num1;
          max=0,b=0;
		 for(j=2;j<=n;j++)
		 {
			 if(b+a[j]<0)
			 {   
				b+=a[j];				
			 }
			 else
			 {			 
				 b=0;
			 }
			 if(b<max)
			 {  
				 max=b;
			 }
		 }
	
        if(num+num2<num-max)
		   num=num-max;
		else num+=num2;
	 cout<<num<<endl;
	}
      
	return 0;
}