1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #define maxn 50005
int n,q;
int a[maxn],g[maxn],tot,cnt;
struct yyy{
int ls,rs,sum,lsum,rsum;
yyy(int a=0,int b=0,int c=0) {sum=a,lsum=b,rsum=c;}
}f[maxn*20];
inline void calc(yyy x,yyy y,yyy &ans) {
ans.sum=x.sum+y.sum;
ans.lsum=max(x.lsum,x.sum+y.lsum);
ans.rsum=max(y.rsum,x.rsum+y.sum);
return ;
}
inline int Update(int l,int r,int pre,int head,int k) {
int rt=++cnt;f[rt]=f[pre];
if (l==r) return f[rt].sum=f[rt].lsum=f[rt].rsum=k,rt;
int mid=l+r>>1;
if (head<=mid) f[rt].ls=Update(l,mid,f[rt].ls,head,k);
else f[rt].rs=Update(mid+1,r,f[rt].rs,head,k);
calc(f[f[rt].ls],f[f[rt].rs],f[rt]);
return rt;
}
const int inf=1e9;
inline yyy Query(int l,int r,int rt,int head,int tail) {
if (!rt) return yyy(-inf,-inf,-inf);
if (head<=l&&r<=tail) return f[rt];
int mid=l+r>>1;
if (head<=mid&&mid<tail) {
yyy tmp1=Query(l,mid,f[rt].ls,head,tail);
yyy tmp2=Query(mid+1,r,f[rt].rs,head,tail);
yyy tmp3;calc(tmp1,tmp2,tmp3);
return tmp3;
}
else if (head<=mid) return Query(l,mid,f[rt].ls,head,tail);
else if (tail>mid) return Query(mid+1,r,f[rt].rs,head,tail);
}
int root[maxn],id[maxn];
inline bool cmp(int x,int y) {return a[x]<a[y];}
vector<int>O[maxn];
signed main(void){
int i;
read(n);
for (i=1;i<=n;i++) read(a[i]),g[i]=a[i];
sort(g+1,g+1+n);
tot=unique(g+1,g+1+n)-g-1;
for (i=1;i<=n;i++) a[i]=lower_bound(g+1,g+1+n,a[i])-g,O[a[i]].push_back(i);
for (i=1;i<=n;i++) root[0]=Update(1,n,root[0],i,1);
for (i=1;i<=tot;i++) {
root[i]=root[i-1];
for (auto tmp:O[i-1])
root[i]=Update(1,n,root[i],tmp,-1);
}
read(q);
int las=0,tmp1,tmp2,tmp3,tmp4,s1,s2,s3;
while (q--) {
for (i=1;i<=4;i++) read(id[i]),id[i]=(id[i]+las)%n+1;
sort(id+1,id+5);
tmp1=id[1],tmp2=id[2],tmp3=id[3],tmp4=id[4];
int l=0,r=tot+1,mid;
while (l+1<r) {
mid=l+r>>1;
s1=s2=s3=0;
if (tmp1<tmp2) s1=Query(1,n,root[mid],tmp1,tmp2).rsum;
if (tmp2+1<tmp3) s2=Query(1,n,root[mid],tmp2+1,tmp3-1).sum;
if (tmp3<tmp4) s3=Query(1,n,root[mid],tmp3,tmp4).lsum;
if (s1+s2+s3>=0) l=mid;
else r=mid;
}
printf("%d\n",las=g[l]);
}
return 0;
}
|