#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int T;
int n;
int a[50001];
int dp[50001];
int big[50001];
int dp2[50001];
int ans;

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