#include <bits/stdc++.h>
#define rep(i,j,k) for(int i = (j);i <= (k);i++)
#define per(i,j,k) for(int i = (j);i >= (k);i--)
#define pii pair<int,int>
#define mkp make_pair
#define eb emplace_back
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define SZ(S) (int)S.size()
using namespace std;

template <class P>
void chkmin(P &x,P y){
    if(x > y) x = y;
}

template <class Q>
void chkmax(Q &x,Q y){
    if(x < y) x = y;
}
int n,q;
int a[250005],b[250005];
ll pre[250005],suf[250005],sum[250005],suma[250005];
int pl[250005],pr[250005],ql[250005],qr[250005],ok[2][250005],sp[250005];

struct node{
    int bas,tag;
    ll sum;
}tree[1000005];
#define ls (rt * 2)
#define rs (rt * 2 + 1)
void upd(int rt,int C){
    tree[rt].sum += 1ll * C * tree[rt].bas;
    tree[rt].tag += C;
}
void pushdown(int rt){
    upd(ls,tree[rt].tag);upd(rs,tree[rt].tag);
    tree[rt].tag = 0;
}
void pushup(int rt){
    tree[rt].bas = tree[ls].bas + tree[rs].bas;
    tree[rt].sum = tree[ls].sum + tree[rs].sum;
}
void modify(int rt,int l,int r,int pos,int C){
    if(l == r){
        tree[rt].bas = C;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt);
    if(pos <= mid) modify(ls,l,mid,pos,C);
    else modify(rs,mid+1,r,pos,C);
    pushup(rt);
}
void upload(int rt,int l,int r,int L,int R,int C){
    if(l == L && r == R){
        upd(rt,C);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt);
    if(R <= mid){
        upload(ls,l,mid,L,R,C);
    }else if(L > mid){
        upload(rs,mid+1,r,L,R,C);
    }else{
        upload(ls,l,mid,L,mid,C);
        upload(rs,mid+1,r,mid+1,R,C);
    }
    pushup(rt);
}
ll query(int rt,int l,int r,int L,int R){
    if(l == L && r == R) return tree[rt].sum;
    int mid = (l + r) >> 1;
    pushdown(rt);
    if(R <= mid) return query(ls,l,mid,L,R);
    else if(L > mid) return query(rs,mid+1,r,L,R);
    else return query(ls,l,mid,L,mid) + query(rs,mid+1,r,mid+1,R);
}
vector <int> sta;
struct qry{
    int l,r,id,op;
};
vector <int> P[250005];
vector <qry> Q[250005];
vector <ll> maxsum(
    std::vector<int> A, std::vector<int> B, 
    std::vector<int> L1, std::vector<int> R1, 
    std::vector<int> L2, std::vector<int> R2){
    n = SZ(A);q = SZ(L1);
    rep(i,1,n){
        a[i] = A[i - 1];
        b[i] = B[i - 1];
    }

    ll ssum = 0;
    pre[0] = -linf;suf[n + 1] = -linf;
    rep(i,1,n){
        ssum = max(ssum,0ll) + a[i];
        pre[i] = max(pre[i - 1],ssum);
    }
    ssum = 0;
    per(i,n,1){
        ssum = max(ssum,0ll) + a[i];
        suf[i] = max(suf[i + 1],ssum);
    }
    rep(i,1,n){
        sum[i] = sum[i - 1] + b[i];
        suma[i] = suma[i - 1] + a[i];
    }
    sta.clear();
    per(i,n,0){
        while(!sta.empty() && sum[i] > sum[sta.back()]) sta.pop_back();
        pl[i + 1] = n + 1;
        int pos = -1;
        per(k,17,0) if(pos + (1 << k) < SZ(sta) && sum[sta[pos + (1 << k)]] >= sum[i] + suf[sta[pos + (1 << k)] + 1]) pos += 1 << k;
        if(pos >= 0) pl[i + 1] = sta[pos];
//        for(int r:sta) if(sum[r] >= sum[i] + suf[r + 1]) chkmin(pl[i + 1],r);
        sta.eb(i);
    }
    sta.clear();
    rep(i,0,n){
        while(!sta.empty() && sum[i] < sum[sta.back()]) sta.pop_back();
        qr[i] = 0;
        int pos = -1;
        per(k,17,0) if(pos + (1 << k) < SZ(sta) && sum[i] >= sum[sta[pos + (1 << k)]] + pre[sta[pos + (1 << k)]]) pos += 1 << k;
        if(pos >= 0) qr[i] = sta[pos] + 1;
//        for(int l:sta) if(sum[i] >= sum[l] + pre[l]) chkmax(qr[i],l + 1);
        sta.eb(i);        
    }

    sta.clear();
    per(i,n,0){
        while(!sta.empty() && sum[i] <= sum[sta.back()]) sta.pop_back();
        if(!sta.empty()) pr[i + 1] = sta.back();
        else pr[i + 1] = n;
        sta.eb(i);
    }

    sta.clear();
    rep(i,0,n){
        while(!sta.empty() && sum[i] >= sum[sta.back()]) sta.pop_back();
        if(!sta.empty()) ql[i] = sta.back() + 1;
        else ql[i] = 1;
        sta.eb(i);
    }
    ll Mn = 0;
    rep(i,1,n){
        if(suma[i - 1] <= Mn) ok[0][i] = 1;
        chkmin(Mn,suma[i]);        
    }
    per(i,n,1) suma[i] = suma[i + 1] + a[i];
    Mn = 0;
    per(i,n,1){
        if(suma[i + 1] <= Mn) ok[1][i] = 1;
        chkmin(Mn,suma[i]);
    }
    rep(i,1,n) if(ok[0][i] && ok[1][i] && max(pre[i - 1],suf[i + 1]) <= b[i]) sp[i] = 1;
    rep(i,1,n){
        if(pl[i] <= pr[i] && ok[0][i]){
            P[pl[i]].eb(i);
            P[pr[i] + 1].eb(-i);
        }
    }
    rep(i,0,q - 1){
        L1[i]++;R1[i]++;
        L2[i]++;R2[i]++;      
        Q[R2[i]].push_back({L1[i],R1[i],i,1});
        Q[L2[i] - 1].push_back({L1[i],R1[i],i,-1});
    }
    vector <ll> ans(q);
    rep(i,1,n){
        chkmin(qr[i],i - 1);
        for(int id:P[i]){
            if(id > 0) modify(1,1,n,id,1);
            else modify(1,1,n,-id,0);
        }
        if(ql[i] <= qr[i] && ok[1][i]) upload(1,1,n,ql[i],qr[i],1);   
        for(qry I:Q[i]) ans[I.id] += I.op * query(1,1,n,I.l,I.r);
    }
/*    rep(l,1,n){
        rep(r,l + 1,n){
            if(pl[l] <= r && r <= pr[l] && ql[r] <= l && l <= qr[r] && ok[0][l] && ok[1][r]) valid[l][r] = 1;
        }
    }
    rep(i,1,n){
        rep(j,1,n) valid[i][j] += valid[i][j - 1];
    }
    rep(i,1,n){
        rep(j,1,n) valid[i][j] += valid[i - 1][j];
    }*/
    rep(i,1,n) sp[i] += sp[i - 1];
    rep(i,0,q - 1){
        int _l = max(L1[i],L2[i]),_r = min(R1[i],R2[i]);
        if(_l <= _r) ans[i] += sp[_r] - sp[_l - 1];
//        ans[i] = valid[R1[i]][R2[i]] - valid[L1[i] - 1][R2[i]] - valid[R1[i]][L2[i] - 1] + valid[L1[i] - 1][L2[i] - 1];
    }
    return ans;
}
/*
g++ maxsum2.cpp grader3.cpp -Wall -Wshadow -Dcxy -Wno-unused-result -O2 -o grader
*/