Sol:
首先注意到答案是具有单调性的，考虑二分答案 \(x\) 解决。
令 $up(l, r, x)/down(l,r,x) $ 是 \([l,r]\) 中 大于等于/小于 \(x\) 的数。
那么对于一个区间 \([l,r]\)，显然中位数 \(\ge x\) 的条件为 \(up(l, r, x) \ge down(l, r, x)\).
变形得到 \(up(l, r, x) - down(l ,r, x) \ge 0\)。于是非常自然的，我们令大于等于 \(x\) 的数为 \(1\)， 小于等于 \(x\) 的数为 \(-1\)。
将区间拆分为 \([l, b], [b+1, c-1], [c,r]\)，求出 \([a,b]\) 中的最大后缀和以及 \([c,r]\) 中的最大前缀和并判断三者加起来是否 \(>0\) 即可.
此时我们可以做到 \((n \log n)\) 回答一次询问。
如何优化呢？
注意到中位数的取值不大于 \(n\) 种可能，我们可以预处理出所有中位数时的序列形态。
先简化一下问题，只考虑一种中位数的时候如何维护查询。显然直接上线段数维护即可。
于是便自然的想到了可持久化线段树了，具体怎么做建议自己想想。
#include<bits/stdc++.h>
#define int long long
#define zsw(x) ((x + lst) % n + 1)
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, a[N], rk[N];
struct data{
int pre, suf, sum;
};
data merge(struct data d1, struct data d2){
data res;
res.sum = d1.sum + d2.sum;
res.pre = max(d1.pre, d1.sum + d2.pre);
res.suf = max(d2.suf, d2.sum + d1.suf);
return res;
}
namespace Persist_tree{
#define mid (l + r >> 1)
struct node{
int ls, rs;
data dat;
}hjt[N << 5];
int root[N], cnt;
void pushup(int o){hjt[o].dat = merge(hjt[hjt[o].ls].dat, hjt[hjt[o].rs].dat);}
void build(int& o, int l, int r){
hjt[++cnt].dat = {-1, -1, -1}; o = cnt;
if(l == r) return;
build(hjt[o].ls, l, mid); build(hjt[o].rs, mid + 1, r);
pushup(o);
}
void add(int pre, int& o, int l, int r, int x){
hjt[++cnt] = hjt[pre]; o = cnt;
if(l == r){hjt[o].dat = (data){1, 1, 1}; return;}
if(x <= mid) add(hjt[pre].ls, hjt[o].ls, l, mid, x);
else add(hjt[pre].rs, hjt[o].rs, mid + 1, r, x);
pushup(o); //cout << l << " " << r << " " << hjt[o].dat.pre << " " << hjt[o].dat.suf << " " << hjt[o].dat.sum << "\n";
}
data querydat(int o, int l, int r, int s, int t){
if(s > t) return {0, 0, 0};
if(s <= l && r <= t) return hjt[o].dat;
bool bls = (s <= mid), brs = (mid < t);
if(bls && brs) return merge(querydat(hjt[o].ls, l, mid, s, t), querydat(hjt[o].rs, mid + 1, r, s, t));
else if(bls) return querydat(hjt[o].ls, l, mid, s, t);
else if(brs) return querydat(hjt[o].rs, mid + 1, r, s, t);
else assert(0);
}
}
using namespace Persist_tree;
vector<int>pos[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], rk[i] = a[i];
sort(rk + 1, rk + n + 1); int Rksiz = unique(rk + 1, rk + n + 1) - (rk + 1);
for(int i = 1; i <= n; i++) a[i] = lower_bound(rk + 1, rk + Rksiz + 1, a[i]) - rk, pos[a[i]].push_back(i);
build(root[Rksiz + 1], 1, n);
for(int i = Rksiz; i > 0; i--){
root[i] = root[i + 1];
for(int j = 0; j < pos[i].size(); j++) add(root[i], root[i], 1, n, pos[i][j]);
}
int T, lst = 0; cin >> T;
int q[5];
while(T--){
int a, b, c, d;
for(int i = 0; i < 4; i++) cin >> q[i], q[i] = zsw(q[i]);
sort(q, q + 4); a = q[0], b = q[1], c = q[2], d = q[3]; //cout << a << " " << b << " " << c << " " << d << "\n";
int l = 1, r = Rksiz, ans = 0;
while(l <= r){
int rank = querydat(root[mid], 1, n, b + 1, c - 1).sum + querydat(root[mid], 1, n, a, b).suf + querydat(root[mid], 1, n, c, d).pre;
// cout << mid << " " << rank << "\n";
if(rank >= 0){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << (lst = rk[ans]) << "\n";
}
return 0;
}