#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;

int main()
{
    int  arr[100010];
    int lr[100010];
    int  rl[100010];
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll sum1=-1000000010,sum2=-1000000010,mx1=-1000000010,mx2=-1000000010;
        ll n,x=0,y=0;
        cin>>n;
        for(int i=0; i<n; i++)scanf("%d",&arr[i]);
        //sum1=arr[0];sum2=arr[n-1];
        for(int i=0; i<n; i++)
        {
            lr[x++]=sum1;
            if(sum1<0)sum1=arr[i];
            else sum1+=arr[i];
            mx1=max(mx1,sum1);

        }
        y=n-1;
        for(int i=n-1; i>=0; i--)
        {

            rl[y--]=sum2;
            if(sum2<0)sum2=arr[i];
            else sum2+=arr[i];
            mx2=max(mx2,sum2);

        }
        ll mx=-1000000010;
        // for(int i=0;i<n;i++)cout<<lr[i]<<" ";
        // cout<<endl;
        // for(int i=0;i<n;i++)cout<<rl[i]<<" ";
        for(int i=0; i<n; i++)
        {
            ll p=lr[i]+rl[i];
            ll x=lr[i];
            ll y=rl[i];
            mx=max(max(mx,p),max(x,y));
        }
        ll ans=max(max(mx1,mx2),mx);
        cout<<ans<<endl;
    }
    return 0;
}