CLJ神牛的可持久化论文的题目，果然厉害
其实第一步能想到后面就还是很简单的
首先是二分答案，转化为判定性问题
然后对于区间内的数，比他大的标为1，小的标为-1
显然，如果存在一个左右端点符合的区间使得这个区间和大于等于0（因为这里中位数是向下取整）
那么中位数一定是大于等于这个数的，这并不难理解
下面我们就是要快速求出左端点在[a,b]，右端点[c,d]的最大区间和
显然可以转化为rmax[a,b]+sum[b+1,c-1]+lmax[c,d]；
这里我们不难想到对于每个数建立一个线段树
线段树就是以位置为索引的，记录着区间左最大，区间右最大和区间和
考虑到树的形态都是相同的，我们可以先对数进行排序，然后建立主席树
平时我们的主席树都是在每个位置上建立一棵以键值为索引的线段树，而这里刚好相反
二分答案后就对对应数的线段树求区间最大和
type node=record
lm,rm,l,r,s:longint;
end; var tree:array[..*] of node;
a,c,h:array[..] of longint;
q:array[..] of longint;
j,m,t,ans,n,mid,i,l,r,w:longint; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure deal;
var i,j:longint;
begin
for i:= to do
for j:=i+ to do
if q[i]>q[j] then swap(q[i],q[j]);
end; procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) shr ];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
swap(c[i],c[j]);
swap(a[i],a[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure update(var a,b,c:node);
begin
a.s:=b.s+c.s;
a.lm:=max(b.lm,b.s+c.lm);
a.rm:=max(c.rm,c.s+b.rm);
end; function build(l,r:longint):longint;
var m,q:longint;
begin
inc(t);
if l=r then
begin
tree[t].s:=;
tree[t].lm:=;
tree[t].rm:=;
exit(t);
end
else begin
m:=(l+r) shr ;
q:=t;
tree[q].l:=build(l,m);
tree[q].r:=build(m+,r);
update(tree[q],tree[tree[q].l],tree[tree[q].r]);
exit(q);
end;
end; function work(l,r,last,x:longint):longint;
var m,q:longint;
begin
inc(t);
if l=r then
begin
tree[t].s:=-;
tree[t].lm:=-;
tree[t].rm:=-;
exit(t);
end
else begin
m:=(l+r) shr ;
q:=t;
if x<=m then
begin
tree[q].r:=tree[last].r;
tree[q].l:=work(l,m,tree[last].l,x);
end
else begin
tree[q].l:=tree[last].l;
tree[q].r:=work(m+,r,tree[last].r,x);
end;
update(tree[q],tree[tree[q].l],tree[tree[q].r]);
exit(q);
end;
end; function ask(l,r,x,ql,qr:longint):node; //传递整个node的的写法比我以前的写法要简单不少
var m:longint;
s,s1,s2:node;
begin
s.lm:=; s.rm:=; s.s:=;
if ql>qr then exit(s);
if (ql<=l) and (qr>=r) then exit(tree[x])
else begin
m:=(l+r) shr ;
if ql>m then exit(ask(m+,r,tree[x].r,ql,qr));
if qr<=m then exit(ask(l,m,tree[x].l,ql,qr));
s1:=ask(l,m,tree[x].l,ql,qr);
s2:=ask(m+,r,tree[x].r,ql,qr);
update(s,s1,s2);
exit(s);
end;
end; begin
readln(n);
for i:= to n do
begin
readln(a[i]);
c[i]:=i;
end;
sort(,n);
h[]:=build(,n);
for i:= to n do
h[i]:=work(,n,h[i-],c[i-]);
readln(m);
for i:= to m do
begin
for j:= to do
begin
read(q[j]);
q[j]:=(q[j]+ans) mod n+;
end;
readln;
deal;
l:=;
r:=n;
while l<=r do //二分答案
begin
mid:=(l+r) shr ;
w:=ask(,n,h[mid],q[],q[]).rm+ask(,n,h[mid],q[],q[]).lm+ask(,n,h[mid],q[]+,q[]-).s;
if w>= then
begin
ans:=a[mid];
l:=mid+;
end
else r:=mid-;
end;
writeln(ans);
end;
end.