孩子心态爆炸了，code：

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
typedef long long ll;
int t,n;ll a[1000005],num[1000005],pre[1000005],nxt[1000005];
struct node{ll p,v;};
bool operator <(const node &x,const node &y){if(x.v!=y.v)return x.v<y.v;return x.p<y.p;}
multiset<node> q;
ll mabs(ll x){return x<0?-x:x;}
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		int now=1,cnt=0;
		while(a[now]==0&&now<=n) now++;
		while(now<=n)
		{
			int od=now;ll tmp=a[od];
			while(now+1<=n&&1ll*a[od]*a[now+1]>=0) now++,tmp+=a[now];
			num[++cnt]=mabs(tmp);now++;
		}
//		cout<<cnt<<endl;for(int i=1;i<=cnt;i++) cout<<num[i]<<" ";cout<<endl;
		ll curs=0,ans=0;
		for(int i=1;i<=cnt;i++) q.insert({i,num[i]}),pre[i]=i-1,nxt[i]=i+1;
		nxt[0]=1;pre[cnt+1]=cnt;
		for(int i=1;i<=cnt;i++)
		{
			if(!q.size()) break;
			auto dq=q.begin();
//			cout<<(*dq).p<<" "<<(*dq).v<<endl;
			ans+=(*dq).v-curs;curs=(*dq).v;q.erase(dq);
			int p=(*dq).p;num[p]=0;
			if(pre[p]==0||nxt[p]==cnt+1)
			{
				pre[nxt[p]]=pre[p];
				nxt[pre[p]]=nxt[p];
				continue;
			}
			// del pre,add nxt
			auto d1=q.find({pre[p],num[pre[p]]});q.erase(d1);
			auto d2=q.find({nxt[p],num[nxt[p]]});q.erase(d2);
			num[nxt[p]]+=num[pre[p]]-curs;num[pre[p]]=0;
			q.insert({nxt[p],num[nxt[p]]});
			nxt[pre[pre[p]]]=nxt[p];
			pre[nxt[p]]=pre[pre[p]];
		}
		cout<<ans<<endl;
		for(int i=1;i<=n;i++) a[i]=0;
		for(int i=0;i<=cnt+1;i++) pre[i]=nxt[i]=num[i]=0;q.clear();
	}
	return 0;
}