记录编号	157579	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]middle	最终得分	100
用户昵称	真呆菌	是否通过	通过
代码语言	C++	运行时间	16.395 s
提交时间	2015-04-09 14:43:35	内存使用	13.64 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#define l(x) T[x].lc
#define r(x) T[x].rc
#define lx(x) T[x].lx
#define rx(x) T[x].rx
#define sx(x) T[x].sx
using namespace std;
const int N = 20010;
struct SegTree{
	int lx,rx,lc,rc,sx;}T[N*30];
struct Seq{
	int x,id;}A[N];
int n,m,tot,root[N];

bool Cmp(const Seq &a,const Seq&b){
	if(a.x<b.x) return 1;
	return 0;
}

int Max(int x,int y){if(x>y) return x;return y;}

SegTree Link(SegTree a,SegTree b){
	SegTree t=(SegTree){0,0,0,0,0};
	t.sx=a.sx+b.sx;
	t.lx=Max(a.lx,a.sx+b.lx);
	t.rx=Max(b.rx,b.sx+a.rx);
	return t;
}

void Update(int x){
	sx(x)=sx(l(x))+sx(r(x));
	lx(x)=Max(lx(l(x)),sx(l(x))+lx(r(x)));
	rx(x)=Max(rx(r(x)),sx(r(x))+rx(l(x)));
	return;
}

int Build(int l,int r){
	int now=++tot,mid;
	if(l==r){
		lx(now)=rx(now)=sx(now)=1;
		return now;
	}
	mid=(l+r)>>1;
	l(now)=Build(l,mid);
	r(now)=Build(mid+1,r);
	Update(now);
	return now;
}

int Change(int x,int l,int r,int a){
	int now=++tot,mid;T[now]=T[x];
	if(l==r){sx(now)=-1;lx(now)=0;rx(now)=0;return now;}
	mid=(l+r)>>1;
	if(a<=mid) l(now)=Change(l(x),l,mid,a);
	else r(now)=Change(r(x),mid+1,r,a);
	Update(now);
	return now;
}

int TQuery(int x,int l,int r,int L,int R){
	if(l>=L&&r<=R) return sx(x);
	int res=0,mid=(l+r)>>1;
	if(L<=mid) res+=TQuery(l(x),l,mid,L,R);
	if(R>mid) res+=TQuery(r(x),mid+1,r,L,R);
	return res;
}

int LQuery(int x,int l,int r,int L,int R){
	if(l>=L&&r<=R) return lx(x);
	int mid=(l+r)>>1;
	if(R<=mid) return LQuery(l(x),l,mid,L,R);
	else if(L>mid) return LQuery(r(x),mid+1,r,L,R);
	else return Max(LQuery(l(x),l,mid,L,R),TQuery(l(x),l,mid,L,R)+LQuery(r(x),mid+1,r,L,R));
}

int RQuery(int x,int l,int r,int L,int R){
	if(l>=L&&r<=R) return rx(x);
	int mid=(l+r)>>1;
	if(R<=mid) return RQuery(l(x),l,mid,L,R);
	else if(L>mid) return RQuery(r(x),mid+1,r,L,R);
	else return Max(RQuery(r(x),mid+1,r,L,R),TQuery(r(x),mid+1,r,L,R)+RQuery(l(x),l,mid,L,R));
}

SegTree TTQuery(int x,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T[x];
	int mid=(l+r)>>1;
	if(R<=mid) return TTQuery(l(x),l,mid,L,R);
	else if(L>mid) return TTQuery(r(x),mid+1,r,L,R);
	return Link(TTQuery(l(x),l,mid,L,R),TTQuery(r(x),mid+1,r,L,R));
}

bool Check(int x,int a,int b,int c,int d){
	int res=0;
	res+=TTQuery(root[x],1,n,b,c).sx;
	res+=TTQuery(root[x],1,n,a,b-1).rx;
	res+=TTQuery(root[x],1,n,c+1,d).lx;
	if(res>=0) return 1;
	return 0;
}

int Query(int a,int b,int c,int d){
	int l=1,r=n,mid;
	while(r-l>1){
		mid=(l+r)>>1;
		if(Check(mid,a,b,c,d)==1) l=mid;
		else r=mid;
	}
	if(Check(r,a,b,c,d)==1) return r;
  	return l;
}

void Paint(int x,int l,int r){
	if(l==r) {printf("%d ",sx(x));return;}
	Paint(l(x),l,(l+r)>>1),Paint(r(x),((l+r)>>1)+1,r);
	return;
}

int main(){
	#define Read
	#ifdef Read
		freopen("nt2012_middle.in","r",stdin);
		freopen("nt2012_middle.out","w",stdout);
	#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&A[i].x);
		A[i].id=i;
	}
	sort(A+1,A+n+1,Cmp);
	root[1]=Build(1,n);
	for(int i=2;i<=n;i++) 
		root[i]=Change(root[i-1],1,n,A[i-1].id);
	scanf("%d",&m);int q[4],ans=0;
	while(m--){
		for(int i=0;i<4;i++) scanf("%d",&q[i]),q[i]=(q[i]+ans)%n+1;
		sort(q,q+4);
		ans=A[Query(q[0],q[1],q[2],q[3])].x;
		printf("%d\n",ans);
	}
	return 0;
}