记录编号	131273	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]middle	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	11.285 s
提交时间	2014-10-24 09:30:07	内存使用	53.95 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZE_TREE=20000*100,SIZEN=20010,INF=0x7fffffff/2;
class NODE{//线段树的节点
public:
	int left,right;
	int lson,rson;
	int sum;
	int mxpre,mxsuf;
	#define left(x) Tree[x].left
	#define right(x) Tree[x].right
	#define lson(x) Tree[x].lson
	#define rson(x) Tree[x].rson
	#define sum(x) Tree[x].sum
	#define mxpre(x) Tree[x].mxpre
	#define mxsuf(x) Tree[x].mxsuf
}Tree[SIZE_TREE];
int tot=0;
void update(NODE &x,NODE &l,NODE &r){
	x.sum=l.sum+r.sum;
	x.mxpre=max(l.mxpre,l.sum+r.mxpre);
	x.mxsuf=max(r.mxsuf,r.sum+l.mxsuf);
}
NODE operator + (NODE a,NODE b){
	NODE x;
	update(x,a,b);
	return x;
}
void update(int x){
	if(x==-1) return;
	if(lson(x)==-1) return;
	update(Tree[x],Tree[lson(x)],Tree[rson(x)]);
}
int build(int a,int b){
	int x=tot++;
	left(x)=a,right(x)=b;
	if(a<b){
		int mid=(a+b)/2;
		lson(x)=build(a,mid);
		rson(x)=build(mid+1,b);
		update(x);
	}
	else{//开始时全是1
		lson(x)=rson(x)=-1;
		sum(x)=mxpre(x)=mxsuf(x)=1;
	}
	return x;
}
int change(int p,int a,int t){//a加上t
	if(left(p)>a||right(p)<a) return p;//无需修改
	int x=tot++;
	Tree[x]=Tree[p];//先复制
	if(left(x)==a&&right(x)==a){
		sum(x)+=t;
		mxpre(x)=mxsuf(x)=sum(x);
	}
	else{
		lson(x)=change(lson(x),a,t);
		rson(x)=change(rson(x),a,t);
		update(x);
	}
	return x;
}
NODE query(int p,int a,int b){
	if(left(p)>=a&&right(p)<=b) return Tree[p];
	int mid=(left(p)+right(p))/2;
	if(a>mid) return query(rson(p),a,b);
	else if(b<=mid) return query(lson(p),a,b);
	return query(lson(p),a,b)+query(rson(p),a,b);
}
int N,Q;
pair<int,int> s[SIZEN];
int root[SIZEN];
bool check(int k,int a,int b,int c,int d){//k是否可能成为[a,b]~[c,d]的中位数
	NODE l,m,r;
	l=query(root[k],a,b);
	if(b+1<=c-1) m=query(root[k],b+1,c-1);
	else m.sum=0;
	r=query(root[k],c,d);
	return l.mxsuf+m.sum+r.mxpre>=0;
}
int calc(int a,int b,int c,int d){
	int l=1,r=N;
	while(l<r){
		int mid=(l+r)/2;
		if(check(mid+1,a,b,c,d)) l=mid+1;
		else r=mid;
	}
	return s[l].first;
}
void work(void){
	scanf("%d",&Q);
	int x=0;
	int q[4];
	while(Q--){
		for(int i=0;i<4;i++){
			scanf("%d",&q[i]);
			q[i]=(q[i]+x)%N;
			q[i]++;
		}
		sort(q,q+4);
		x=calc(q[0],q[1],q[2],q[3]);
		printf("%d\n",x);
	}
}
void make_tree(void){
	sort(s+1,s+1+N);
	root[1]=build(1,N);
	for(int i=2;i<=N;i++)
		root[i]=change(root[i-1],s[i-1].second,-2);
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%d",&s[i].first);
		s[i].second=i;
	}
}
int main(){
	freopen("nt2012_middle.in","r",stdin);
	freopen("nt2012_middle.out","w",stdout);
	read();
	make_tree();
	work();
	return 0;
}