首先，对于每个询问，我们二分答案
然后对于序列中大于等于中位数的数，我们把它们置为1，小于中位数的数，置为-1
那么如果一个区间和大于等于0，那么就资磁，否则就不滋磁
这个区间和呢，我们可以用主席树维护前缀和
[c,d]上的最大前缀和减去[a-1,b-1]上的最小前缀和，就是所有可用区间的最大区间和
这样要求主席树支持区间修改，正好之前没写过（捂脸），练一下
复杂度O(nlog^2n)
（如果不资磁区间修改的话，也可以通过维护最大/小连续和的那套理论，达到同样的效果（好像所有题解都是这么做的））
（当然首先要离散化……）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define N 23333 using namespace std;
inline int read(){
int ret=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while ('0'<=ch&&ch<='9'){
ret=ret*10-48+ch;
ch=getchar();
}
return ret;
} struct STnode{
int ls,rs;
int maxv,minv;
int tag;
}; int n,root[N];
struct SegmentTree{
STnode t[12333666];
int size;
inline int newnode(int x){t[++size]=t[x];return size;}
void PushUp(int x){
t[x].maxv=max(t[t[x].ls].maxv,t[t[x].rs].maxv);
t[x].minv=min(t[t[x].ls].minv,t[t[x].rs].minv);
}
void add(int &x,int delta){
x=newnode(x);
t[x].maxv+=delta;t[x].minv+=delta;t[x].tag+=delta;
}
void PushDown(int x){
if (!t[x].ls) t[x].tag=0;
if (t[x].tag){
add(t[x].ls,t[x].tag);add(t[x].rs,t[x].tag);
t[x].tag=0;
}
}
void build(int x,int l,int r){
t[x].tag=t[x].ls=t[x].rs=0;
if ((t[x].minv=l)==(t[x].maxv=r)) return;
int mid=(l+r)/2;
build(t[x].ls=++size,l,mid);
build(t[x].rs=++size,mid+1,r);
}
int clear(){build(size=1,1,n);return 1;}
void modify(int &x,int L,int R,int l,int r,int delta){
PushDown(x);
if (l<=L&&R<=r){add(x,delta);return;}
x=newnode(x);
int mid=(L+R)/2;
if (l<=mid) modify(t[x].ls,L,mid,l,r,delta);
if (r>mid) modify(t[x].rs,mid+1,R,l,r,delta);
PushUp(x);
}
int qmin(int x,int L,int R,int l,int r){
PushDown(x);
if (l<=L&&R<=r) return t[x].minv;
int mid=(L+R)/2;
if (r<=mid) return qmin(t[x].ls,L,mid,l,r);
if (l>mid) return qmin(t[x].rs,mid+1,R,l,r);
return min(qmin(t[x].ls,L,mid,l,r),qmin(t[x].rs,mid+1,R,l,r));
}
int qmax(int x,int L,int R,int l,int r){
PushDown(x);
if (l<=L&&R<=r) return t[x].maxv;
int mid=(L+R)/2;
if (r<=mid) return qmax(t[x].ls,L,mid,l,r);
if (l>mid) return qmax(t[x].rs,mid+1,R,l,r);
return max(qmax(t[x].ls,L,mid,l,r),qmax(t[x].rs,mid+1,R,l,r));
}
} st; int query(int a,int b,int c,int d){
int l=1,r=n+1,mid;
while (l+1<r){
mid=(l+r)/2;
int tmpr=st.qmax(root[mid],1,n,c,d);
int tmpl=st.qmin(root[mid],1,n,max(a-1,1),b-1);
if (a==1) tmpl=min(tmpl,0);
if (tmpr-tmpl>=0) l=mid;
else r=mid;
}
return l;
} int a[N];
struct num{
int value,pos;
num(){}
num(int _value,int _pos):value(_value),pos(_pos){}
} tt[N];
inline bool operator <(const num &x,const num &y){
return x.value<y.value;
} int main(){
n=read();
for (int i=1;i<=n;++i) tt[i]=num(a[i]=read(),i);
sort(tt+1,tt+n+1); root[1]=st.clear();
for (int i=1;i<n;++i)
st.modify(root[i+1]=root[i],1,n,tt[i].pos,n,-2); int lastans=0,q[4];
for (int Q=read();Q;Q--){
for (int k=0;k<4;++k) q[k]=(read()+lastans)%n+1;
sort(q,q+4);
lastans=tt[query(q[0],q[1],q[2],q[3])].value;
printf("%d\n",lastans);
}
return 0;
}