CF1787I

来个单调栈+SGT 做法。

首先题意显然可以转化为求所有 $b$ 的前缀和的最大值加上最大子段和。求前缀和的最值的和是简单的，这里不细讲，维护个单调栈二分即可。

考虑怎么求所有区间 $[l,r]$ 的最大子段和之和。考虑从大到小枚举 $l$，对于每个 $r$ 维护两个值，$f_j$ 表示 $[i,j]$ 内的最大子段的左端点，$w_j$ 表示 $[i,j]$ 内的最大子段和。显然 $l_j$ 和 $w_j$ 都是单调不减的。

考虑 $l\to l-1$ 会有什么影响。首先某一些 $j$ 的 $l_j$ 此时会变成 $i$，并且根据上面的结论，这一定是 $[l,n]$ 的一段前缀。然后发现，进行完这些 $l_j$ 的更新后 $w_j$ 变大，可能会有 $w_k<w_j(k>j)$，那么就让 $[i,k]$ 的最大子段变成 $[i,j]$ 的，也就是 $l_j\to l_k,w_j\to w_k$。最后还有可能有一些 $[i.j]$ 的最大子段变成 $[i,i]$。

然后就考虑维护这些操作。设 $s_i=\sum_{j<i}a_j$。首先，$i\to l_j$ 当且仅当 $s_{i-1}<s_{l_j-1}$，于是把 $l_j$ 一样的 $j$ 放在一起，用单调栈维护，找出所有 $i\to l_j$ 的位置。还要考虑 $s_{l_j-1}$ 带来的变化，这相当于区间 $+s_{l_j-1}-s_{i-1}$。

然后考虑改变后面的 $k$ 时怎么维护，容易发现这个 $k$ 还是一个区间，于是二分找到最后一个 $k$，区间推平。变成 $[i,i]$ 的 $j$ 也是类似地是一个区间。

于是要支持的操作就是区间加，二分，区间推平，同时每次还要求 $[i,n]$ 的和。于是 SGT 维护区间 $w_j$ 的最大值和区间和即可。

时间复杂度 $O(n\log n)$。跑得飞慢。模拟赛上被卡了。

code：

int n,m,top,St[N];
pii b[N];
ll f[N],a[N],c[N],s[N];
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
struct node{
	int l,r;
	ll w;
}st[N];
struct SGT{
	ll tr[N<<2],s[N<<2],tagA[N<<2],tagF[N<<2];
	il void up(int u){
		tr[u]=max(tr[u<<1],tr[u<<1|1]);
		s[u]=s[u<<1]+s[u<<1|1];
	}
	il void upd(int l,int r,int u,ll k){
		tagA[u]+=k;
		tr[u]+=k,s[u]+=(r-l+1)*k;
	}
	il void fill(int l,int r,int u,ll k){
		tagA[u]=0,tagF[u]=k;
		tr[u]=k,s[u]=(r-l+1)*k;
	}
	il void down(int l,int r,int u){
		int mid=(l+r)>>1;
		if(tagF[u]>-1e9){
			fill(l,mid,u<<1,tagF[u]),fill(mid+1,r,u<<1|1,tagF[u]);
			tagF[u]=-inf;
		}
		upd(l,mid,u<<1,tagA[u]),upd(mid+1,r,u<<1|1,tagA[u]);
		tagA[u]=0;
	}
	void bld(int l,int r,int u){
		tagA[u]=0,tagF[u]=-inf;
		if(l==r){
			tr[u]=-1ll*inf*inf,s[u]=0;
			return;
		}
		int mid=(l+r)>>1;
		bld(l,mid,u<<1),bld(mid+1,r,u<<1|1);
		up(u);
	}
	void upd(int l,int r,int u,int x,int y,ll k){
		if(l>=x&&r<=y){
			upd(l,r,u,k);
			return;
		}
		down(l,r,u);
		int mid=(l+r)>>1;
		if(x<=mid){
			upd(l,mid,u<<1,x,y,k);
		}
		if(y>mid){
			upd(mid+1,r,u<<1|1,x,y,k);
		}
		up(u);
	}
	void fill(int l,int r,int u,int x,int y,ll k){
		if(l>=x&&r<=y){
			fill(l,r,u,k);
			return;
		}
		down(l,r,u);
		int mid=(l+r)>>1;
		if(x<=mid){
			fill(l,mid,u<<1,x,y,k);
		}
		if(y>mid){
			fill(mid+1,r,u<<1|1,x,y,k);
		}
		up(u);
	}
	int fd(int l,int r,int u,ll k){
		if(l==r){
			return l;
		}
		down(l,r,u);
		int mid=(l+r)>>1;
		if(tr[u<<1]<=k){
			return fd(mid+1,r,u<<1|1,k);
		}
		return fd(l,mid,u<<1,k);
	}
	int fd(int l,int r,int u,int x,int y,ll k){
		if(tr[u]<=k){
			return 0;
		}
		if(l>=x&&r<=y){
			return fd(l,r,u,k);
		}
		down(l,r,u);
		int mid=(l+r)>>1,ret=0;
		if(x<=mid){
			if(ret=fd(l,mid,u<<1,x,y,k)){
				return ret;
			}
		}
		if(y>mid){
			return fd(mid+1,r,u<<1|1,x,y,k);
		}
		return 0;
	}
	ll qry(int l,int r,int u,int x,int y){
		if(r<x||l>y){
			return 0;
		}
		if(l>=x&&r<=y){
			assert(s[u]>=0);
			return s[u];
		}
		down(l,r,u);
		int mid=(l+r)>>1;
		return qry(l,mid,u<<1,x,y)+qry(mid+1,r,u<<1|1,x,y);
	}
}T;
void Yorushika(){
	read(n);
	rep(i,1,n){
		read(a[i]);
		f[i]=f[i-1]+a[i];
	}
	T.bld(1,n,1);
	int ans=0;
	top=0;
	drep(i,n,1){
		int p=i;ll tmp=0;
		int cur=0;
		while(top&&st[top].w>=f[i-1]){
			node t=st[top--];
			T.upd(1,n,1,t.l,t.r,t.w-f[i-1]);
			b[++cur]=Mp(t.l,t.r),p=t.r;
		}
		drep(j,cur,1){
			int p=b[j].se;ll tmp=T.qry(1,n,1,p,p);
			int q=T.fd(1,n,1,p+1,n,tmp);
			if(!q)q=n+1;
			while(top&&st[top].r<q){
				top--;
			}
			if(top&&st[top].l<q){
				st[top].l=q;
			}
			T.fill(1,n,1,p,q-1,tmp);
			st[++top]={b[j].fi,q-1,f[i-1]};
		}
		p=T.fd(1,n,1,i+1,n,max(a[i],0ll));
		if(!p)p=n+1;
		while(top&&st[top].r<p){
			top--;
		}
		if(top&&st[top].l<p){
			st[top].l=p;
		}
		st[++top]={i,p-1,f[i-1]};
		T.fill(1,n,1,i,p-1,max(a[i],0ll));
		while(top>1&&st[top-1].w==st[top].w){
			st[top-1].l=min(st[top-1].l,st[top].l);
			st[top-1].r=max(st[top-1].r,st[top].r);
			top--;
		}
		ans=Mod(ans,(T.qry(1,n,1,i,n)%mod+mod)%mod);
	}
	top=0;
	St[0]=n+1;
	ll sum=0;
	drep(i,n,1){
		while(top&&f[St[top]]<f[i]){
			top--;
		}
		St[++top]=i;
		s[top]=s[top-1]+(St[top-1]-St[top])*f[St[top]];
		int l=1,r=top,p=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(f[St[mid]]>=f[i-1]){
				p=mid;
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
		ans=Mod(ans,(s[p]-(n-St[p]+1)*f[i-1])%mod);
	}
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	read(t);
	while(t--){
		Yorushika();
	}
}