经典的二分答案 \(mid\)，\(\ge mid\) 的数权值为 1，\(<mid\) 权值为 -1，答案合法当且仅当存在区间 \([l,r]\) 使得权值和 \(\ge 0\)，做前缀和 \(s\)，即等价于 \(s_r-s_{l-1}\ge 0\to s_r\ge s_{l-1}\)。
对于询问 \((a,b,c,d)\) 只需要 \(\max_{i=c}^ds_i\ge \min_{i=a-1}^{b-1}s_i\) 即可，所以预处理对于 \(mid\) 的所有情况下对应的区间 \(s\) 最值。。
主席树，对于序列 \(a\) 中每种数开一个版本，\(mid=a_i\) 情况下 \(s\) 数组的情况即为在 \(A\) （\(A\) 大于 \(a_i\) 的最小值）版本的基础上将所有 \(a_i\) 插入，即后缀加。所以主席树只用实现区间加、查询区间最值，可以标记永久化实现。
- 当询问 \(a=0\) 时 \(\min_{i=a-1}^{b-1}s_i\) 要与 \(0\) 取 \(\min\)。
::::info[code]
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define Cinout ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
const int N=2e4+5,inf=1e9;
int a[N],b[N],tot,rt[N],Q[4];vector<int>q[N];
struct node{int ls,rs,mx,mn,laz;}tr[N<<8];
void pushup(int u){tr[u].mx=max(tr[tr[u].ls].mx,tr[tr[u].rs].mx)+tr[u].laz,tr[u].mn=min(tr[tr[u].ls].mn,tr[tr[u].rs].mn)+tr[u].laz;
}
void upd(int &idx,int id,int l,int r,int lf,int d){if(idx==id||!idx)tr[idx=++tot]=tr[id];int mid=l+r>>1;if(l>=lf){if(tr[idx].mx==-inf)tr[idx].mx=d;else tr[idx].mx+=d;if(tr[idx].mn==inf)tr[idx].mn=d;else tr[idx].mn+=d;tr[idx].laz+=d;return;}if(lf<=mid)upd(tr[idx].ls,tr[id].ls,l,mid,lf,d);upd(tr[idx].rs,tr[id].rs,mid+1,r,lf,d);pushup(idx);
}
int query_mx(int u,int l,int r,int lf,int rt,int s){if(!u)return s;int mid=l+r>>1,res=-inf;if(l>=lf&&r<=rt)return tr[u].mx+s;if(lf<=mid)res=max(res,query_mx(tr[u].ls,l,mid,lf,rt,s+tr[u].laz));if(rt>mid)res=max(res,query_mx(tr[u].rs,mid+1,r,lf,rt,s+tr[u].laz));return res;
}
int query_mn(int u,int l,int r,int lf,int rt,int s){if(lf<0)lf=0;if(!u)return s;int mid=l+r>>1,res=inf;if(l>=lf&&r<=rt)return tr[u].mn+s;if(lf<=mid)res=min(res,query_mn(tr[u].ls,l,mid,lf,rt,s+tr[u].laz));if(rt>mid)res=min(res,query_mn(tr[u].rs,mid+1,r,lf,rt,s+tr[u].laz));return res;
}
inline void Solve(){int n;cin>>n;for(int i=0;i<n;i++)cin>>a[i],b[i]=a[i];sort(b,b+n);int len=unique(b,b+n)-b-1;for(int i=0;i<n;i++)q[lower_bound(b,b+len,a[i])-b].pb(i);for(int i=0;i<n;i++)upd(rt[len+1],rt[len+1],0,n-1,i,-1);for(int i=len;~i;i--)for(int j:q[i])upd(rt[i],rt[i+1],0,n-1,j,2);int q,lst=0;cin>>q;while(q--){cin>>Q[0]>>Q[1]>>Q[2]>>Q[3];for(int i:{0,1,2,3})Q[i]=(Q[i]+lst)%n;sort(Q,Q+4);int l=0,r=len,mid;while(l<=r)(mid=l+r>>1,query_mx(rt[mid],0,n-1,Q[2],Q[3],0)>=min((Q[0]==0?0:inf),query_mn(rt[mid],0,n-1,Q[0]-1,Q[1]-1,0))?l=mid+1:r=mid-1);cout<<(lst=b[l-1])<<'\n';}
}
signed main(){
// freopen("tst.in","r",stdin);
// freopen("tst.out","w",stdout);Cinout;int _=1;for(;_;_--)Solve();return 0;
}::::