#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define N 120000 #define MAX 1000000005 int n,m,x,cnt,l,r,ans,tmp,root[N],sum[N*30],ls[N*30],rs[N*30]; int getint(){ char ch; int sum=0; for (ch=getchar();ch<'0' || ch>'9';ch=getchar()); for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0'; return sum; } void ins(int &rt,int rt2,int l,int r,int k){ if (!rt) sum[rt=++cnt]=sum[rt2]; if (l==r){sum[rt]+=k; return;} int mid=(l+r)>>1; if (k<=mid){rs[rt]=rs[rt2]; ins(ls[rt],ls[rt2],l,mid,k);} if (k>mid){ls[rt]=ls[rt2]; ins(rs[rt],rs[rt2],mid+1,r,k);} sum[rt]=sum[ls[rt]]+sum[rs[rt]]; } int query(int rt,int l,int r,int L,int R){ if (!rt) return 0; if (l>=L && r<=R) return sum[rt]; int mid=(l+r)>>1,ret=0; if (L<=mid) ret+=query(ls[rt],l,mid,L,R); if (R>mid) ret+=query(rs[rt],mid+1,r,L,R); return ret; } int main(){ n=getint(); for (int i=1;i<=n;i++){x=getint(); ins(root[i],root[i-1],1,MAX,x);} m=getint(); for (int i=1;i<=m;i++){ l=getint(); r=getint(); ans=1; while ((tmp=query(root[r],1,MAX,1,ans)-query(root[l-1],1,MAX,1,ans))>=ans) ans=tmp+1; printf("%d\n",ans); } return 0; }
|