Description：

询问左端点在 $[a,b]$ 之间，右端点在 $[c,d]$ 之间的子序列中，最大的中位数。其中 $a<b<c<d$ 。强制在线。

$1 \le n \le 20000$ $1\le q \le 25000$

Solution：

先二分答案，对于序列中的数字，如果大于等于 $mid$ ，赋成 $1$ ，小于 $mid$ ，赋成 $-1$ ，这样只要判断是否有一段的和 $\ge 0$ ，如果有，则这一段的中位数可以变得更大。求最大子段和可以用线段树维护，但开不下 $n$ 棵线段树，于是用主席树，预处理出对于每个数线段树的形态，由于改变一个数只有这个叶子结点到根的一条链发生变化，所以每次把一条链上的 $1$ 改成 $-1$ ，然后就可以二分了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 20010

int a[MAXN],b[MAXN],s[MAXN];

bool cmp(int x,int y){return a[x] < a[y];}

struct node

{

	int lc,rc,lsum,rsum,sum;

	node(){lsum = rsum = sum = 0;}

}t[MAXN * 15 * 2];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

#define mid ((l + r) >> 1)

void merge(node &rt,node lc,node rc)

{

	rt.sum = lc.sum + rc.sum;

	rt.lsum = max(lc.lsum,lc.sum + rc.lsum);

	rt.rsum = max(rc.rsum,rc.sum + lc.rsum);

	return;

}

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r){t[rt].lsum = t[rt].rsum = t[rt].sum = 1;return;}

	build(t[rt].lc,l,mid);build(t[rt].rc,mid + 1,r);

	merge(t[rt],t[t[rt].lc],t[t[rt].rc]);

	return;

}

void add(int &rt,int rt_,int k,int l,int r)

{

	rt = newnode();t[rt] = t[rt_];

	if(l == r){t[rt].sum = -1;t[rt].lsum = t[rt].rsum = 0;return;}

	if(k <= mid)add(t[rt].lc,t[rt_].lc,k,l,mid);

	else add(t[rt].rc,t[rt_].rc,k,mid + 1,r);

	merge(t[rt],t[t[rt].lc],t[t[rt].rc]);

	return;

}

node query(int rt,int L,int R,int l,int r)

{

	if(L > R){node temp;return temp;}

	if(L <= l && r <= R)return t[rt];

	if(R <= mid)return query(t[rt].lc,L,R,l,mid);

	if(L >= mid + 1)return query(t[rt].rc,L,R,mid + 1,r);

	node res;

	merge(res,query(t[rt].lc,L,R,l,mid),query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

void pt(int rt,int l,int r)

{

	if(l == r){cout << t[rt].sum << " ";return;}

	pt(t[rt].lc,l,mid);

	pt(t[rt].rc,mid + 1,r);

	return;

}

inline int maxsum(int k,int a1,int b1,int c1,int d1)

{

	return query(root[k],a1,b1 - 1,1,n).rsum + query(root[k],b1,c1,1,n).sum + query(root[k],c1 + 1,d1,1,n).lsum;

}

int main()

{

	scanf("%d",&n);

	for(register int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(register int i = 1;i <= n;++i)b[i] = i;

	sort(b + 1,b + 1 + n,cmp);

	for(register int i = 1;i <= n;++i)s[b[i]] = i;

	build(root[1],1,n);

	for(register int i = 2;i <= n;++i)add(root[i],root[i - 1],b[i - 1],1,n);

	int lastans = 0;

	int q[5];

	scanf("%d",&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d%d",&q[1],&q[2],&q[3],&q[4]);

		for(int k = 1;k <= 4;++k)q[k] = (q[k] + lastans) % n + 1;

		sort(q + 1,q + 1 + 4);

		int l = 1,r = n,cen;

		while(l < r)

		{

			cen = ((l + r + 1) >> 1);

			if(maxsum(cen,q[1],q[2],q[3],q[4]) >= 0)l = cen;

			else r = cen - 1;

		}

		cout << (lastans = a[b[l]]) << endl;

	}

	return 0;

}