#include<iostream>

using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

const int MAXN = 52000;
int tcase,n,ans,a[MAXN],dp1[MAXN],dp2[MAXN];

int main()
{
    scanf("%d",&tcase);while(tcase--)
    {
        scanf("%d",&n);
        for(int i=1;n-i>=0;i++) scanf("%d",&a[i]);
        
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        
        for(int i=1;n-i>=0;i++) dp1[i]=max(a[i],dp1[i-1]+a[i]);
        for(int i=n;i-1>=0;i--) dp2[i]=max(a[i],dp2[i+1]+a[i]);
        
        for(int i=2;n-i>=0;i++) dp1[i]=max(dp1[i],dp1[i-1]);
        for(int i=n-1;i>=1;i--) dp2[i]=max(dp2[i],dp2[i+1]);
        
        ans=dp1[1]+dp2[2];
        for(int i=2;n-i>=0;i++) ans=max(ans,dp1[i-1]+dp2[i]);
        printf("%d\n",ans);
    }
    return 0;
}