#include <iostream>
using namespace std;
#define max(a,b) ((a>b)?(a):(b))
int a[50001];//数据数组
int dpy[50001];//前i个数的1个子串的最大值,,必包含第i个..
int dpn[50001];//前i个数的1个子串的最大值,,不必包含第i个..
int dp2[50001];//前i个数的2个子串的最大值,必包含第i个...
int main()
{
	int t;
	for(scanf("%d",&t);t--;)
	{
		int n;
		scanf("%d",&n);
		int i;
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		dpy[0]=dpn[0]=-1000000;
		for(i=1;i<=n;i++)
		{
			dpy[i]=max(dpy[i-1]+a[i],a[i]);
			dpn[i]=max(dpy[i],dpn[i-1]);
		}
		int ans=INT_MIN;
		dp2[1]=a[1];
		for(i=2;i<=n;i++)
		{
			dp2[i]=max(dpn[i-1]+a[i],dp2[i-1]+a[i]);
			ans=max(dp2[i],ans);
		}
		printf("%d\n",ans);
	}
	return 0;
}