RT，一直 WA 30 也不知道为什么……

#include <algorithm>
#include <cstdio>
#include <vector>
#define inf 100000000

using namespace std;

int cnt, rt[20002];
struct node{
	int l, r, pmax, smax, sum;
}tr[20000001];
inline void pushup(int u){
	tr[u].pmax = max(tr[tr[u].l].pmax, tr[tr[u].l].sum + tr[tr[u].r].pmax);
	tr[u].smax = max(tr[tr[u].r].smax, tr[tr[u].l].smax + tr[tr[u].r].sum);
	tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}
void update(int u1, int& u2, int l, int r, int p, int x){
	if (!u2) u2 = ++ cnt;
	if (l == r){
		tr[u2].pmax = tr[u2].smax = tr[u2].sum = x;
		return;
	}
	int mid = l + r >> 1;
	if (p <= mid) tr[u2].r = tr[u1].r, update(tr[u1].l, tr[u2].l, l, mid, p, x);
	else tr[u2].l = tr[u1].l, update(tr[u1].r, tr[u2].r, mid + 1, r, p, x);
	pushup(u2);
}
node query(int u, int l, int r, int L, int R){
	if (R < l || r < L) return {0, 0, -inf, -inf, 0};
	if (L <= l && r <= R) return tr[u];
	int mid = l + r >> 1;
	node a = query(tr[u].l, l, mid, L, R), b = query(tr[u].r, mid + 1, r, L, R);
	return {0, 0, max(a.pmax, a.sum + b.pmax), max(b.smax, a.smax + b.sum), a.sum + b.sum};
}

int n, q, a[20002], _, b[20002], t[4], ll, lr, rl, rr, ans;
vector<int> p[20002];
void build(int &u, int l, int r){
	u = ++ cnt;
	if (l == r){
		tr[u] = {0, 0, -1, -1, -1};
		return;
	}
	int mid = l + r >> 1;
	build(tr[u].l, l, mid);
	build(tr[u].r, mid + 1, r);
	pushup(u);
}
bool check(int x){
	int tmp = 0;
	if (lr + 1 <= rl - 1) tmp = query(rt[x], 1, n, lr + 1, rl - 1).sum;
	int A = query(rt[x], 1, n, ll, lr).smax, B = query(rt[x], 1, n, rl, rr).pmax;
	return A + tmp + B >= 0;
}
int main(){
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]), b[++ _] = a[i];
	sort(b + 1, b + _ + 1);
	_ = unique(b + 1, b + _ + 1) - b - 1;
	for (int i = 1;i <= n;i ++) a[i] = lower_bound(b + 1, b + _ + 1, a[i]) - b;
	for (int i = 1;i <= n;i ++) p[a[i]].push_back(i);
	build(rt[_ + 1], 1, n);
	for (int i = _;i >= 1;i --){
		for (int j = 0;j < p[i].size();j ++){
			update(rt[i + 1], rt[i], 1, n, p[i][j], 1);
		}
	}
	scanf("%d", &q);
	while (q --){
		scanf("%d%d%d%d", &ll, &lr, &rl, &rr);
		t[0] = (ll + ans) % n + 1, t[1] = (lr + ans) % n + 1, t[2] = (rl + ans) % n + 1, t[3] = (rr + ans) % n + 1;
		sort(t, t + 4);
		ll = t[0], lr = t[1], rl = t[2], rr = t[3];
		int l = 1, r = _ + 1;
		while (r - l > 1){
			int mid = l + r >> 1;
			if (check(mid)) l = mid;
			else r = mid;
		}
		printf("%d\n", ans = b[l]);
	}
}