以后再也不写分块了 /kk

#include <bits/stdc++.h>
using namespace std;

const int N = 2e4 + 5, M = 150;
int n, a[N], Q; int len, b[N];
int lst, q[5];

int o(int i, int x) { return a[i] < x ? -1 : 1; }
namespace ArrayDiv {
	int B, tot, L[M], R[M], bel[N];
	int sum[M][N], pre[M][N], suf[M][N];
	void init() {
		memset(sum, -0x3f, sizeof sum); memset(pre, -0x3f, sizeof pre); memset(suf, -0x3f, sizeof suf);
		B = sqrt(n); tot = (n - 1) / B + 1;
		for (int i = 1; i <= tot; i++) L[i] = R[i - 1] + 1, R[i] = B * i; R[tot] = n;
		for (int i = 1; i <= tot; i++) {
			for (int j = L[i]; j <= R[i]; j++) {
				bel[j] = i;
				int now = 0, x = a[j];
				for (int k = L[i]; k <= R[i]; k++) now += o(k, x), pre[i][x] = max(pre[i][x], now);
				sum[i][x] = now; now = 0;
				for (int k = R[i]; k >= L[i]; k--) now += o(k, x), suf[i][x] = max(suf[i][x], now);
			}
			for (int x = len; x >= 1; x--) {
				sum[i][x] = max(sum[i][x], sum[i][x + 1]);
				pre[i][x] = max(pre[i][x], pre[i][x + 1]);
				suf[i][x] = max(suf[i][x], suf[i][x + 1]);
//				cout << sum[i][x] << ' ' << pre[i][x] << ' ' << suf[i][x] << '\n';
			}
		}
	}
	int getsum(int l, int r, int x) {
		int p = bel[l], q = bel[r], now = 0;
		if (p == q) {
			for (int i = l; i <= r; i++) now += o(i, x);
			return now;
		}
		for (int i = l; i <= R[p]; i++) now += o(i, x);
		for (int i = p + 1; i <= q - 1; i++) now += sum[i][x];
		for (int i = L[q]; i <= r; i++) now += o(i, x);
		return now;
	}
	int getpre(int l, int r, int x) {
		int p = bel[l], q = bel[r], now = 0, mx = 0;
		if (p == q) {
			for (int i = l; i <= r; i++) now += o(i, x), mx = max(mx, now);
			return mx;
		}
		for (int i = l; i <= R[p]; i++) now += o(i, x), mx = max(mx, now);
		for (int i = p + 1; i <= q - 1; i++) mx = max(mx, now + pre[i][x]), now += sum[i][x];
		for (int i = L[q]; i <= r; i++) now += o(i, x), mx = max(mx, now);
		return mx;
	}
	int getsuf(int l, int r, int x) {
		int p = bel[l], q = bel[r], now = 0, mx = 0;
		if (p == q) {
			for (int i = r; i >= l; i--) now += o(i, x), mx = max(mx, now);
			return mx;
		}
		for (int i = r; i >= L[q]; i--) now += o(i, x), mx = max(mx, now);
		for (int i = q - 1; i >= p + 1; i--) mx = max(mx, now + suf[i][x]), now += sum[i][x];
		for (int i = R[p]; i >= l; i--) now += o(i, x), mx = max(mx, now);
		return mx;
	}
} using namespace ArrayDiv;

bool check(int x) { return getsuf(q[1], q[2], x) + getsum(q[2] + 1, q[3] - 1, x) + getpre(q[3], q[4], x) >= 0; }

int main() {
//	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
	sort(b + 1, b + n + 1); len = unique(b + 1, b + n + 1) - (b + 1);
	for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
	init();
	for (cin >> Q; Q--; ) {
		for (int i = 1; i <= 4; i++) cin >> q[i], q[i] = (q[i] + lst) % n + 1;
		sort(q + 1, q + 4 + 1);
		int l = 1, r = len;
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		cout << (lst = b[l]) << '\n';
	}
	return 0;
}

/*
5
2 3 9 1 1 
1
3 2 2 2
*/