判断中位数是否可行需要将当前的解作为分界，大于其的置为1，小于为-1，然后b-c必选，ab，cd可不选，这个用线段树判定就好

但不能每次跑，所以套主席树，按权值排序，构建主席树，更新时将上一个节点改为-1，能保证以上结论

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#define N 20005

using namespace std;

int lon[32*N],ron[32*N],sum[32*N],maxl[32*N],maxr[32*N];

int n,m,sz,num[N],num_cnt,root[N];

template<typename _t>

inline _t read(){

	_t x=0,f=1;

	char ch=getchar();

	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-f;

	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);

	return x*f;

}

struct data{

	int val,id;

	bool operator <(const data &a)const{return a.val>val;}

}d[N];

void print(int x,int l,int r){

	if(!x)return ;

	printf("%4d  %4d  %4d  %4d  l=%4d  r=%4d  %4d  %4d\n",x,l,r,sum[x],maxl[x],maxr[x],lon[x],ron[x]);

	int mid=(l+r)>>1;

	print(lon[x],l,mid);

	print(ron[x],mid+1,r);

}

void pushup(int rt){

	maxl[rt]=max(maxl[lon[rt]],sum[lon[rt]]+maxl[ron[rt]]);

	maxr[rt]=max(maxr[ron[rt]],sum[ron[rt]]+maxr[lon[rt]]);

	sum[rt]=sum[lon[rt]]+sum[ron[rt]];

}

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

	rt=++sz;

	if(l==r){sum[rt]=maxl[rt]=maxr[rt]=1;return;}

	int mid=(l+r)>>1;

	build(lon[rt],l,mid);

	build(ron[rt],mid+1,r);

	pushup(rt);

}

void insert(int p,int &rt,int l,int r,int x,int y){

	rt=++sz;

	lon[rt]=lon[p]; ron[rt]=ron[p];

	if(l==r){sum[rt]=maxl[rt]=maxr[rt]=y;return;}

	int mid=(l+r)>>1;

	if(x<=mid) insert(lon[p],lon[rt],l,mid,x,y);

	else insert(ron[p],ron[rt],mid+1,r,x,y);

	pushup(rt);

}

int query(int rt,int l,int r,int x,int y){

	if(l>=x&&r<=y) return sum[rt];

	int ans=0;

	int mid=(l+r)>>1;

	if(x<=mid) ans+=query(lon[rt],l,mid,x,y);

	if(y>mid) ans+=query(ron[rt],mid+1,r,x,y);

	return ans;

}

int getmaxr(int rt,int l,int r,int x,int y){

	if(l==x&&r==y) return maxr[rt];

	int mid=(l+r)>>1,ans=0;

	if(y<=mid) return getmaxr(lon[rt],l,mid,x,y);

	if(x>mid) return getmaxr(ron[rt],mid+1,r,x,y);

	else return max(getmaxr(ron[rt],mid+1,r,mid+1,y),getmaxr(lon[rt],l,mid,x,mid)+query(ron[rt],mid+1,r,mid+1,y));

}

int getmaxl(int rt,int l,int r,int x,int y){

	if(l==x&&r==y) return maxl[rt];

	int mid=(l+r)>>1,ans=0;

	if(y<=mid) return getmaxl(lon[rt],l,mid,x,y);

	if(x>mid) return getmaxl(ron[rt],mid+1,r,x,y);

	else return max(getmaxl(lon[rt],l,mid,x,mid),query(lon[rt],l,mid,x,mid)+getmaxl(ron[rt],mid+1,r,mid+1,y));

}

bool judge(int x,int a,int b,int c,int d){

	int ans=0;

	if(c>b+1)ans+=query(root[x],1,n,b+1,c-1);

	ans+=getmaxr(root[x],1,n,a,b);

	ans+=getmaxl(root[x],1,n,c,d);

	if(ans>=0) return 1;

	return 0;

}

int gy()

{

	freopen("nt2012_middle.in","r",stdin);

	freopen("nt2012_middle.out","w",stdout);

	n=read<int>();

	for(int i=1;i<=n;i++){

		d[i].val=read<int>();

		num[i]=d[i].val;

		d[i].id=i;

	}

	sort(num+1,num+n+1);

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

		d[i].val=lower_bound(num+1,num+n+1,d[i].val)-num;

	sort(d+1,d+n+1);

	/*for(int i=1;i<=n;i++)

		printf("%d  %d\n",i,d[i].val);*/

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

	for(int i=2;i<=n;i++)

		insert(root[i-1],root[i],1,n,d[i-1].id,-1);

	/*for(int i=1;i<=n;i++){

		printf("i=========%d\n",i);

		print(root[i],1,n);

	}*/

	scanf("%d",&m);

	int a[4];

	int ans=0;

	while(m--){

		for(int i=0;i<4;i++){a[i]=read<int>();a[i]=(a[i]+ans)%n+1;}

		sort(a,a+4);

		int L=1,R=n,mid;

		while(L+1<R){

			mid=(L+R)>>1;

			if(judge(mid,a[0],a[1],a[2],a[3])) L=mid;

			else R=mid;

		}

		if(judge(R,a[0],a[1],a[2],a[3])) ans=num[R];

		else ans=num[L];

		printf("%d\n",ans);

	}

	return 0;

}

int ryf=gy();

int main(){;}