题意：一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。
给你一个长度为n的序列s。
回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
其中a<b<c<d。
位置也从0开始标号。
我会使用一些方式强制你在线。
n<=20000,Q<=25000
思路:RYZ上课讲的题，第一次做这种类型的主席树，以前只会序列第K大，树上第K大，维护二维前缀和之类的……
这道题的精髓是用主席树保存每个点被更改后的N个版本
对于一段区间与一个数X，如果区间中的数a[i]>=x则b[i]=1，否则-1
易得：若某一段中b[i]总和>=0则必定可以从其中取出一段中位数为X的序列，则X可以作为答案
反之显然答案具有单调性，子段和最大的一段一定可以构造出最大的中位数
查询时判断queryr(a,b)+querysum(b+1,c-1)+queryl(c,d)是否>=0即可
剩下的二分X与最大子段和，最大左右子段和维护部分已经在各种各样的地方（NOI Plus模拟赛）做了不下10遍了
而且还有各种写法不同难度的，比如暴力，RMQ之类的
这题就是单点修改+线段树版本的
强制从0开始标号P党表示不爽
var t:array[..,..]of longint;
root,lx,rx,sum:array[..]of longint;
a,b,d:array[..]of longint;
n,que,i,j,cnt,l,r,last,lastans,mid:longint; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; procedure qsort(l,r:longint);
var i,j,mid:longint;
begin
i:=l; j:=r; mid:=a[(l+r)>>];
repeat
while mid>a[i] do inc(i);
while mid<a[j] do dec(j);
if i<=j then
begin
swap(a[i],a[j]);
swap(b[i],b[j]);
inc(i); dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end; procedure sort;
var i,j:longint;
begin
for i:= to do
for j:= to -i do
if d[j]>d[j+] then swap(d[j],d[j+]);
end; procedure pushup(p:longint);
var l,r:longint;
begin
l:=t[p,]; r:=t[p,];
lx[p]:=max(lx[l],sum[l]+lx[r]);
rx[p]:=max(rx[r],sum[r]+rx[l]);
sum[p]:=sum[l]+sum[r];
end; procedure build(var p:longint;l,r:longint);
var mid:longint;
begin
inc(cnt); p:=cnt;
if l=r then
begin
lx[p]:=; rx[p]:=; sum[p]:=;
exit;
end;
mid:=(l+r)>>;
build(t[p,],l,mid);
build(t[p,],mid+,r);
pushup(p);
end; procedure update(l,r:longint;var p:longint;v,x:longint);
var mid:longint;
begin
inc(cnt); t[cnt]:=t[p]; lx[cnt]:=lx[p]; rx[cnt]:=rx[p]; sum[cnt]:=sum[p];
p:=cnt;
if l=r then
begin
sum[p]:=x; lx[p]:=x; rx[p]:=x;
exit;
end;
mid:=(l+r)>>;
if v<=mid then update(l,mid,t[p,],v,x)
else update(mid+,r,t[p,],v,x);
pushup(p);
end; function querysum(l,r,x,y,p:longint):longint;
var mid,s:longint;
begin
if (l=x)and(r=y) then exit(sum[p]);
mid:=(l+r)>>;
s:=;
if y<=mid then s:=querysum(l,mid,x,y,t[p,])
else if x>mid then s:=querysum(mid+,r,x,y,t[p,])
else s:=querysum(l,mid,x,mid,t[p,])+
querysum(mid+,r,mid+,y,t[p,]);
exit(s);
end; function queryleft(l,r,x,y,p:longint):longint;
var mid,s:longint;
begin
if (l=x)and(r=y) then exit(lx[p]);
mid:=(l+r)>>;
s:=;
if y<=mid then s:=queryleft(l,mid,x,y,t[p,])
else if x>mid then s:=queryleft(mid+,r,x,y,t[p,])
else s:=max(queryleft(l,mid,x,mid,t[p,]),
querysum(l,mid,x,mid,t[p,])+
queryleft(mid+,r,mid+,y,t[p,]));
exit(s);
end; function queryright(l,r,x,y,p:longint):longint;
var mid,s:longint;
begin
if (l=x)and(r=y) then exit(rx[p]);
mid:=(l+r)>>;
s:=;
if y<=mid then s:=queryright(l,mid,x,y,t[p,])
else if x>mid then s:=queryright(mid+,r,x,y,t[p,])
else s:=max(queryright(mid+,r,mid+,y,t[p,]),
querysum(mid+,r,mid+,y,t[p,])+
queryright(l,mid,x,mid,t[p,]));
exit(s);
end; function isok(k,a,b,c,d:longint):boolean;
var s:longint;
begin
s:=;
if b+<=c- then s:=querysum(,n-,b+,c-,root[k]);
s:=s+queryright(,n-,a,b,root[k]);
s:=s+queryleft(,n-,c,d,root[k]);
exit(s>=);
end; begin read(n);
for i:= to n do
begin
read(a[i]); b[i]:=i;
end;
qsort(,n); build(root[],,n-);
for i:= to n do
begin
root[i]:=root[i-];
update(,n-,root[i],b[i]-,-);
end;
read(que);
for i:= to que do
begin
for j:= to do read(d[j]);
for j:= to do d[j]:=(d[j]+lastans) mod n;
sort;
l:=; r:=n; last:=;
while l<=r do
begin
mid:=(l+r)>>;
if isok(mid,d[],d[],d[],d[]) then begin last:=mid; l:=mid+; end
else r:=mid-;
end;
lastans:=a[last+];
writeln(lastans);
end; end.