#include<stdio.h>
int b[50001][2];
int a[50001];
void dyn(int n)
{
     b[0][0]=a[0];
     b[0][1]=a[n-1];
     int i;
     for(i=1;i<n;i++)
                     if(b[i-1][0]>0)b[i][0]=b[i-1][0]+a[i];
                     else
                     b[i][0]=a[i];
     for(i=1;i<n;i++)
     if(b[i-1][1]>0)b[i][1]=b[i-1][1]+a[n-1-i];
     else
     b[i][1]=a[n-1-i];
     for(i=1;i<n;i++)
     if(b[i-1][1]>b[i][1])b[i][1]=b[i-1][1];
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
              int n;
              scanf("%d",&n);
              int i,j;
              for(i=0;i<n;i++)
              scanf("%d",&a[i]);
              dyn(n);
              int max=-10000001;
              int temp;
              for(i=0;i<n-1;i++)
              {
                              if(b[i][0]+b[n-2-i][1]>max)max=b[i][0]+b[n-2-i][1];
                              }
              printf("%d\n",max);
              }
              return 0;
}
                              
能过。