rt,TLE On test 14。可能是平衡树中的合并Join写错了，玄关。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
    auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
    auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = long double;using ldb = long double;
#define int ll
const int N = 1e6 + 10;
int n,m,p,a[N],tid[N],ans[N],st[N];
vector<int> Ad[N],De[N];
struct FHQ_Treap{
    struct node{
        int ls,rs,siz,fa,pri;
        ll val,lz;
        int id;
        node(int L,int R,int S,int F,ll V,int P,ll Z):
            ls(L),rs(R),siz(S),fa(F),val(V),pri(P),lz(Z){};
    };vector<node> t;
#define ls(x) t[x].ls
#define rs(x) t[x].rs
#define siz(x) t[x].siz
#define fa(x) t[x].fa
#define val(x) t[x].val
#define pri(x) t[x].pri
#define lz(x) t[x].lz
#define eb emplace_back
    int tot,rt;
    FHQ_Treap(){tot = 0,rt = 0;t.eb(0,0,0,0,0,0,0);}
    int New(int val){t.eb(0,0,1,0,val,rand(),0);tot++;return tot;}
    void P(int p){
        siz(p) = siz(ls(p)) + siz(rs(p)) + 1;
        fa(p) = 0;
        if(ls(p)) fa(ls(p)) = p;
        if(rs(p)) fa(rs(p)) = p;
    }
    void mk(int p,ll val){if(!p) return;val(p) += val,lz(p) += val;}
    void D(int p){if(lz(p)) mk(ls(p),lz(p)),mk(rs(p),lz(p)),lz(p) = 0;}
    void split(int p,int val,int &x,int &y){
        if(!p) return x = y = 0,void();D(p);
        if(val(p) <= val) x = p,split(rs(p),val,rs(x),y);
        else y = p,split(ls(p),val,x,ls(y));P(p);
    }
    int Merge(int x,int y){
        if(!x || !y) return x|y;
        D(x);D(y);
        if(pri(x) < pri(y)) return D(x),rs(x) = Merge(rs(x),y),P(x),x;
        else return D(y),ls(y) = Merge(x,ls(y)),P(y),y;
    }
    int Join(int x,int y){
        if(!x || !y) return x|y;
        D(x);D(y);
        if(pri(x) > pri(y)) swap(x,y);
        int a,b;split(y,val(x),a,b);
        ls(x) = Join(ls(x),a);
        rs(x) = Join(rs(x),b);
        return P(x),x;
    }
    int Insert(int val){
        int x,y;split(rt,val,x,y);
        int id = New(val);
        rt = Merge(Merge(x,id),y);
        return id;
    }
    ll get(int id){
        int num = 0;
        for(;id && (st[++num] = id);id = fa(id));
        drep(i,num,1,1) D(st[i]);
        return val(st[1]);
    }
    void upd(int val){
        int x,y;mk(rt,val);
        split(rt,p-1,x,y);mk(y,-p);
        rt = Join(x,y);
    }
    void print(int x){
        D(x);
        cerr<<x<<": "<<val(x)<<' '<<t[x].id<<' '<<fa(x)<<'\n';
        if(ls(x)) print(ls(x));
        if(rs(x)) print(rs(x));
    }
#undef ls
#undef rs
#undef siz
#undef fa
#undef val
#undef pri
#undef lz
#undef eb
}fhq;
pair<int,int> qry[N];
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    srand(24320);
    cin>>n>>m>>p;rep(i,1,n,1) cin>>a[i];
    rep(i,1,m,1){
        int l,r;cin>>l>>r;
        // qry[i] = make_pair(l,r);
        Ad[l].emplace_back(i);
        De[r].emplace_back(i);
    }
    rep(i,1,n,1){
        for(auto id:Ad[i]){
            tid[id] = fhq.Insert(0);
        }
        fhq.upd(a[i]);
        for(auto id:De[i]) ans[id] = fhq.get(tid[id]);
    }
    rep(i,1,m,1) cout<<ans[i]<<'\n';
}