#include <stdio.h>
#include <stdlib.h>
#define bigger(a,b) (a>b?a:b)
int t;
int list[50000+2],fa[50000+2],fb[50000+2],fans[50000+2];
int main()
{
    scanf("%d",&t);
    for (int outi=0;outi<t;outi++)
    {
        int i,max,n;
        scanf("%d",&n);
        for (i=1;i<=n;i++)
            scanf("%d",&list[i]);
        fa[1]=list[1];
        fb[n]=list[n];
        for (i=2;i<=n;i++)
            fa[i]=bigger(list[i],fa[i-1]+list[i]);
        for (i=n-1;i>=1;i--)
            fb[i]=bigger(list[i],fb[i+1]+list[i]);
        fans[n]=fb[n];
        for (i=n-1;i>=1;i--)
            fans[i]=bigger(fans[i+1],fb[i]);
        max=-9999999;
        for (i=2;i<=n;i++)
            if (fans[i]+fa[i-1]>max)    max=fans[i]+fa[i-1];
        printf("%d\n",max);
        for (i=0;i<=n;i++)
            list[i]=fa[i]=fb[i]=fans[i]=0;
    }
}