#include <bits/stdc++.h>
using namespace std;
#define f(a,b,c) for(int a=b;a<c;a++)
typedef pair<int,int> pii;
int a[500000],n,t,sum,msum,i,j;
priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > pq;

int main(){
	cin>>t;
	while(t--){
		while(!pq.empty())pq.pop();
		scanf("%d",&n);
		f(k,0,n)scanf("%d",&a[k]);
		msum=0;
		sum=0;i=0;j=0;
		while(i<n&&j<n){
			//cout<<msum<<endl;
			msum=max(sum,msum);
			if(sum<0){
				if(i!=pq.top().second)sum-=a[i];
				else{pq.pop();
					while(!pq.empty()&&pq.top().second<i)pq.pop();
					sum-=pq.top().first;
				}
				i++;
			}else{
				if(a[j]>=0)sum+=a[j];
				else{
					pq.push(make_pair(a[j],j));
					if(pq.top().second!=j){
						sum+=a[j];
					}
				}
				j++;
			}
			msum=max(sum,msum);
		}
		while(i<n){msum=max(sum,msum);
				if(i!=pq.top().second)sum-=a[i];
				else{pq.pop();
					while(!pq.empty()&&pq.top().second<i)pq.pop();
					sum-=pq.top().first;
				}
				i++;
		}cout<<msum;
	}
}