记录编号	363016	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]middle	最终得分	100
用户昵称	核糖核酸	是否通过	通过
代码语言	C++	运行时间	9.125 s
提交时间	2017-01-09 20:28:45	内存使用	38.77 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <algorithm>
#define N 20005
using namespace std;
inline int read() {
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
int n, Q, ans, q[4], A[N], Index = 0;
pair<int,int> h[N];
map<int,int> root_id;
int T[N];
struct Node {
	int Lc, Rc;
	int Sum, Lsum, Rsum;
} s[N*100];

void Build(int p, int Le, int Re) {
	if(Le == Re) {s[p].Sum = s[p].Lsum = s[p].Rsum = 1; return;}
	int mid = (Le + Re) >> 1;
	s[p].Lc = ++Index; s[p].Rc = ++Index;
	Build(s[p].Lc, Le, mid); Build(s[p].Rc, mid+1, Re);
	s[p].Sum = s[s[p].Lc].Sum + s[s[p].Rc].Sum;
	s[p].Lsum = s[p].Rsum = s[p].Sum;
}

void Insert(int p, int p1, int Le, int Re, int x) {
	s[p].Lc = s[p1].Lc; s[p].Rc = s[p1].Rc;
	if(Le == Re) { s[p].Sum = -1; s[p].Lsum = s[p].Rsum = 0; return; }
	int mid = (Le + Re) >> 1;
	if(x <= mid) s[p].Lc = ++Index; else s[p].Rc = ++Index;
	if(x <= mid) Insert(s[p].Lc, s[p1].Lc, Le, mid, x);
	else Insert(s[p].Rc, s[p1].Rc, mid+1, Re, x);
	s[p].Sum = s[s[p].Lc].Sum + s[s[p].Rc].Sum;
	s[p].Lsum = max(0, max(s[s[p].Lc].Lsum, s[s[p].Lc].Sum + s[s[p].Rc].Lsum));
	s[p].Rsum = max(0, max(s[s[p].Rc].Rsum, s[s[p].Rc].Sum + s[s[p].Lc].Rsum));
}

int Query_sum(int p, int Le, int Re, int l, int r) {
	if(Le == l && Re == r) return s[p].Sum;
	int mid = (Le + Re) >> 1;
	if(r <= mid) return Query_sum(s[p].Lc, Le, mid, l, r);
	else if(l > mid) return Query_sum(s[p].Rc, mid+1, Re, l, r);
	else return Query_sum(s[p].Lc,Le,mid,l,mid) + Query_sum(s[p].Rc,mid+1,Re,mid+1,r);
}

int Query_Lsum(int p, int Le, int Re, int l, int r) {
	if(Le == l && Re == r) return s[p].Lsum;
	int mid = (Le + Re) >> 1;
	if(r <= mid) return Query_Lsum(s[p].Lc, Le, mid, l, r);
	else if(l > mid) return Query_Lsum(s[p].Rc, mid+1, Re, l, r);
	else return max(Query_Lsum(s[p].Lc, Le, mid, l, mid), Query_sum(s[p].Lc, Le, mid, l, mid) + Query_Lsum(s[p].Rc, mid+1, Re, mid+1, r));
}

int Query_Rsum(int p, int Le, int Re, int l, int r) {
	if(Le == l && Re == r) return s[p].Rsum;
	int mid = (Le + Re) >> 1;
	if(r <= mid) return Query_Rsum(s[p].Lc, Le, mid, l, r);
	else if(l > mid) return Query_Rsum(s[p].Rc, mid+1, Re, l, r);
	else return max(Query_Rsum(s[p].Rc, mid+1, Re, mid+1, r), Query_sum(s[p].Rc, mid+1, Re, mid+1, r) + Query_Rsum(s[p].Lc, Le, mid, l, mid));
}

void Pre_work() {
	sort(h+1, h+n+1);

	T[0] = ++Index;
	Build(T[0], 1, n);
	for(int i=1; i<=n; i++) {
		T[i] = ++Index;
		root_id[h[i].first] = T[i];
		Insert(T[i], T[i-1], 1, n, h[i].second);
	}
	
	for(int i=n; i>=1; i--) {
		while(h[i].first == h[i-1].first) i--;
		root_id[h[i].first] = root_id[h[i-1].first];
	}
	
	root_id[h[1].first] = T[0];
}

bool check(int id) {
	int sum = Query_sum(id, 1, n, q[1], q[2]);
	if(q[0] != q[1]) sum += Query_Rsum(id, 1, n, q[0], q[1]-1);
	if(q[2] != q[3]) sum += Query_Lsum(id, 1, n, q[2]+1, q[3]);
	return sum >= 0;
}

int main() {
	freopen("nt2012_middle.in", "r", stdin);
	freopen("nt2012_middle.out", "w", stdout);
	
	n = read();
	for(int i=1; i<=n; i++) {
		A[i] = read();
		h[i] = make_pair(A[i], i);
	}
	
	Pre_work();
	
	Q = read(); ans = 0;
	while(Q--) {
		for(int i=0; i<4; i++) q[i] = (read() + ans) % n + 1;
		sort(q, q+4);
		int l = 1, r = n;
		while(l <= r) {
			int mid = (l + r) >> 1;
			int id = root_id[h[mid].first];
			if(check(id)) { ans = h[mid].first; l = mid+1; }
			else r = mid-1;
		}
		printf("%d\n", ans);
	}

	return 0;
}