主席树模板，麻烦大佬们帮调一下

#include<bits/stdc++.h>
#define N 1000010
#define Ls t[p].ls
#define Rs t[p].rs
#define ll long long
using namespace std;
int n, Q;
ll a[N], id[N], ans=0;
int root[N], cnt;
int q[4];
struct tree{
    int ls, rs;
    ll lmax, rmax, sum;
}t[N<<3], date;
inline int read(){
    char ch=getchar(); int x=0, f=1;
    while(!isdigit(ch)) {f=(ch=='-')?-1:1; ch=getchar();}
    while(isdigit(ch)) {x=x*10+(ch-'0'); ch=getchar();}
    return x*f;
}
bool cmp(int x, int y){
    return a[x]<a[y];
}
void pushup(int p){
    t[p].sum = t[Ls].sum+t[Rs].sum;
    t[p].lmax = max(t[Ls].lmax, t[Ls].sum+t[Rs].lmax);
    t[p].rmax = max(t[Rs].rmax, t[Rs].sum+t[Ls].rmax);
}
void build(int &p, int l, int r){
    if(!p) p = ++cnt;
    t[p].sum = r-l+1;
    t[p].lmax = t[p].rmax =  r-l+1;
    if(l==r) return ;
    int mid=l+r>>1;
    build(Ls, l, mid);
    build(Rs, mid+1, r);
}
void modify(int &np, int p, int l, int r, int pos){
    np = ++cnt;
    if(l==r){
        t[np].sum=t[np].lmax=t[np].rmax=-1;
        return ;    
    }
    t[np] = t[p];
    int mid = l+r>>1;
    if(pos <= mid) modify(t[np].ls, Ls, l, mid, pos);
    else modify(t[np].rs, Rs, mid+1, r, pos);
    pushup(np);
}
void query(int p, int l, int r, int L, int R){
    if(l>=L && r<=R){
         date.sum += t[p].sum;
         date.lmax = max(date.lmax, date.sum+t[p].lmax);
         date.rmax = max(t[p].rmax, date.rmax+t[p].sum);
         //顺序先左后右，所以可以这样写
         return ;
    }
    int mid = l+r>>1;
    if(L<=mid) query(Ls, l, mid, L, R);
    if(R>mid) query(Rs, mid+1, r, L, R);
}
bool check(int mid){
    //找到满足条件的能使得区间和最大的[l, r]，若此区间和大于等于0，那a[id[mid]]小于等于“中位数”
    ll res=0;
    date.lmax=-1e18, date.rmax=-1e18, date.sum=0;//date作为每次答案查询的“暂存点”，记得每次query都得清零
    if(q[1]+1<=q[2]-1) query(root[mid], 1, n, q[1]+1, q[2]-1); res += date.sum;
    date.lmax=-1e18, date.rmax=-1e18, date.sum=0;
    query(root[mid], 1, n, q[0], q[1]); res += date.rmax;
    date.lmax=-1e18, date.rmax=-1e18, date.sum=0;
    query(root[mid], 1, n, q[2], q[3]); res += date.lmax;
    return res>=0;

}
int main()
{
    freopen("middle.in", "r", stdin);
    freopen("middle.out", "w", stdout);
    n=read();
    for(int i=1; i<=n; i++)
        a[i]=read(), id[i]=i;
    sort(id+1, id+n+1, cmp);
    build(root[1], 1, n);//对于最小的数，所有数都是1
    for(int i=2; i<=n; i++)
        modify(root[i], root[i-1], 1, n, id[i-1]);
        //对每一个序列中的数建一个1/-1的新序列，rt[i]与rt[i-1]的区别就在于，a[id[i-1]]在后者中为1，在前者中应该为0，所以每次就改这一个就行
    Q=read();
    while(Q--){
        for(int i=0; i<4; i++) q[i] = (read()+ans)%n+1;
        sort(q, q+4);
        int l=1, r=n;
        while(l<=r){
            int mid = l+r>>1;
            if(check(mid)) ans = a[id[mid]], l=mid+1;
            else r=mid-1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}