记录编号	446182	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]middle	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.701 s
提交时间	2017-09-07 19:45:47	内存使用	382.90 MiB

//二分答案,若改位数值>=ans,则为1,否则为0;
//若最大子区间和>=0则合法
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=2e7+10;
struct node{int l,r,sum,maxl,maxr;}nd[M];
int root[N],id=3;//root[i]表示>=a[i+1]的线段树
#define lc nd[x].l
#define rc nd[x].r
void update(int x){
    nd[x].sum=nd[lc].sum+nd[rc].sum;
    nd[x].maxl=max(nd[lc].maxl,nd[lc].sum+nd[rc].maxl);
    nd[x].maxr=max(nd[rc].maxr,nd[rc].sum+nd[lc].maxr);
}
int add(int x,int l,int r,int p,int d){
    int now=++id;
    nd[now]=nd[x];
    if (l==r){
        nd[now].sum+=d;
        nd[now].maxl=nd[now].maxr=max(nd[now].sum,0);
        return now;
    }
    int mid=(l+r)>>1;
    if (p>mid) nd[now].r=add(rc,mid+1,r,p,d);
        else nd[now].l=add(lc,l,mid,p,d);
    update(now);
    return now;
}
void query(int x,int l,int r,int L,int R){
    if (l>=L&&r<=R){
        nd[2]=nd[1];nd[3]=nd[x];
        nd[1].l=2;nd[1].r=3;
        update(1);
        return;
    }
    int mid=(l+r)>>1;
    if (L<=mid) query(lc,l,mid,L,R);
    if (R>mid) query(rc,mid+1,r,L,R);
}
int n,Q,a[N],sa[N];
bool cmp(int x,int y){return a[x]<a[y];}
bool test(int rt,int a,int b,int c,int d){
    nd[1]=(node){0,0,0,0,0};
    query(rt,1,n,b,c);
    int sum=nd[1].sum;
    //printf("[%d,%d] sum=%d\n",b,c,sum);
    nd[1]=(node){0,0,0,0,0};
    query(rt,1,n,a,b-1);
    sum+=nd[1].maxr;
    nd[1]=(node){0,0,0,0,0};
    query(rt,1,n,c+1,d);
    sum+=nd[1].maxl;
    //printf("%d\n",sum);
    return sum>=0;
}
int query(int a,int b,int c,int d){
    int l=1,r=n;
    while (l<r){
        int mid=(l+r)>>1;
        //printf("query(>=%d)=",::a[sa[mid+1]]);
        if (test(root[mid],a,b,c,d)) l=mid+1;else r=mid;
    }
    return ::a[sa[l]];
}
int main()
{
    freopen("nt2012_middle.in","r",stdin);
    freopen("nt2012_middle.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),sa[i]=i;
    sort(sa+1,sa+n+1,cmp);
    for (int i=1;i<=n;i++) root[0]=add(root[0],1,n,i,1);
    for (int i=1;i<=n;i++) root[i]=add(root[i-1],1,n,sa[i],-2);
    scanf("%d",&Q);
    int ans=0,q[10];
    while (Q--){
        for (int i=0;i<4;i++) scanf("%d",&q[i]),q[i]=(q[i]+ans)%n+1;
        sort(q,q+4);
        //for (int i=0;i<4;i++) printf("%d ",q[i]);puts("");
        printf("%d\n",ans=query(q[0],q[1],q[2],q[3]));
    }
    return 0;
}