注意到这什么 \(s>q\) 或 \(t\le q\) 的限制条件是没有用的，因为如果 \(s\le q<t\) 你直接 \(\text{swap}(q,t)\) 即可，于是问题转化为对于所有区间 \([l,r]\) 计算其最大前缀和与最大子段和之和。
前者是容易的，相当于 \(\max\limits_{l-1\le i\le r}\{sum_i\}-sum_{l-1}\)，单调栈或者暴力 ST 表建笛卡尔树皆可。
考虑后者，等价于 \(\max\limits_{l-1\le L\le R\le r}sum_R-sum_L\)。这是一个静态数区间问题，一般做法有扫描右端点维护左端点信息 和 离线静态分治两种做法，这里咱们考虑后者。假设分治到区间 \([l,r]\)，计算跨 \(mid\) 的答案，那么我们预处理 \(f_r,mx_r,g_l,mn_l\) 分别表示 \([mid+1,r]\) 的答案，\([mid,r]\) 中 \(sum\) 的最大值，\([l,mid]\) 的答案，\([l,mid]\) 中 \(sum\) 的最小值。那么易知 \([L,R]\) 的答案是 \(\max\{f_R,g_L,mx_R-mn_L\}\)。可以使用 two pointers + 树状数组做，这样是 2log 的，但是我没卡过去。不过类比 CF1458F，我们发现其实是有决策单调性的啊！即对于固定的 \(L\)，肯定是先一段 \(g_L\)，再一段 \(mx_R-mn_L\)，再一段 \(f_R\)，并且三段分界点随着 \(L\) 的递增是单调递减的，于是直接 two pointers 即可，复杂度 1log。
const int MAXN=1e6;
const int MOD=998244353;
int n,a[MAXN+5],res,num;ll sum[MAXN+5],key[MAXN+5],uni[MAXN+5];
int getpos(int x){return lower_bound(uni+1,uni+num+1,x)-uni;}
void solve1(){
static int stk[MAXN+5];int tp=0,ss=0;stk[tp]=n+1;
for(int i=n;~i;i--){
while(tp&&sum[stk[tp]]<sum[i]){
ss=(ss-sum[stk[tp]]%MOD*(stk[tp-1]-stk[tp])%MOD+MOD)%MOD;
--tp;
}stk[++tp]=i;
ss=(ss+sum[i]%MOD*(stk[tp-1]-stk[tp]))%MOD;
res=(0ll+res+ss-1ll*(n-i+1)*sum[i]%MOD+MOD)%MOD;
}
}
void solve2(int l,int r){
if(l==r){res=(res+max(a[l],0))%MOD;return;}
int mid=l+r>>1;solve2(l,mid);solve2(mid+1,r);
static ll mn[MAXN+5],mx[MAXN+5],f[MAXN+5],g[MAXN+5];
mn[mid+1]=mx[mid]=sum[mid];f[mid+1]=g[mid]=0;
ll cur=-1e18;
for(int i=mid;i>=l;i--){
mn[i]=min(mn[i+1],sum[i-1]);chkmax(cur,sum[i]);
f[i]=max(f[i+1],cur-sum[i-1]);
}cur=1e18;
for(int i=mid+1;i<=r;i++){
mx[i]=max(mx[i-1],sum[i]);chkmin(cur,sum[i-1]);
g[i]=max(g[i-1],sum[i]-cur);
}
int s1=0,s2=0,p=mid+1,q=mid+1;
for(int i=mid+1;i<=r;i++)s1=(s1+g[i])%MOD;
for(int i=mid;i>=l;i--){
while(p<=r&&f[i]>=max(g[p],mx[p]-mn[i]))s2=(s2-mx[p]%MOD+MOD)%MOD,p++;
while(q<=r&&(q<p||mx[q]-mn[i]>=g[q]))s1=(s1-g[q]%MOD+MOD)%MOD,s2=(s2+mx[q])%MOD,q++;
res=(res+f[i]%MOD*(p-mid-1))%MOD;res=(res-mn[i]%MOD*(q-p)%MOD+MOD)%MOD;
res=(res+s1)%MOD;res=(res+s2)%MOD;
}
}
void solve(){
scanf("%d",&n);res=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
num=0;for(int i=0;i<=n;i++)key[i+1]=sum[i];
sort(key+1,key+n+2);key[0]=-1e18;
for(int i=1;i<=n+1;i++)if(key[i]!=key[i-1])uni[++num]=key[i];
solve1();solve2(1,n);printf("%d\n",(res+MOD)%MOD);
}
int main(){
int qu;scanf("%d",&qu);while(qu--)solve();
return 0;
}