#include<iostream>
#include<stdio.h>

using namespace std;
int flag[50001],num[50001];//两个数组分别记录最大和和这个整数序列
const int MIN=-999999999;
int main(){
    int n;
    int ans,i,j;
    int sum,temp;
    int per;
    cin>>n;
    while(n--){


        sum=0,temp=MIN;
        cin>>per;
        for(i=1;i<=per;i++){//从左到右
            scanf("%d",&num[i]);
            sum+=num[i];
            if(sum>temp) {temp = sum;}//分别选出1~i段的最大和，只有所有元素相加的和大于原来的最大和才更新这个最大和
            flag[i]=temp;
            if(sum<0) sum=0;//如果sum出现了负数，就抛弃这一段

        }
        sum=0;
        ans=MIN;
        temp=MIN;
        for(j=per;j>1;j--){//从右到左
            sum+=num[j];
            if(sum>temp) temp=sum;
            if(ans<flag[j-1]+temp) ans=temp+flag[j-1];//序列中的元素和分别与记录好的各段最大和相加，选出其中最大值即为所求
            if(sum<0)sum=0;
        }
        printf("%d\n",ans);

    }
    return 0;
}