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
| #include<bits/stdc++.h>
#define REG register
#define MAXN 100005
using namespace std;
inline int read(){
REG int x(0);
REG char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x*10)+(c^48),c=getchar();
return x;
}
int n,m;
int a[MAXN];
int tot,rt[MAXN];
#define Ls(now) (t[now].ls)
#define Rs(now) (t[now].rs)
#define mid ((l+r)>>1)
struct Tree{
int val,ls,rs;
}t[MAXN<<8];
void Ins(int pre,int& now,int l,int r,int x){
now=++tot;
t[now].val=t[pre].val+x;
Ls(now)=Ls(pre),Rs(now)=Rs(pre);
if(l^r)
if(mid>=x) Ins(Ls(pre),Ls(now),l,mid,x);
else Ins(Rs(pre),Rs(now),mid+1,r,x);
}
int Ask(int L,int R,int l,int r,int x,int y){
if(l>=x&&r<=y) return t[R].val-t[L].val;
int res=0;
if(mid>=x) res+=Ask(Ls(L),Ls(R),l,mid,x,y);
if(mid<y) res+=Ask(Rs(L),Rs(R),mid+1,r,x,y);
return res;
}
void Init(){
n=read();
for(REG int i=1;i<=n;++i)
Ins(rt[i-1],rt[i],1,1000000000,read());
}
void Work(int l,int r){
int pos=1,res;
while(res^pos){
res=Ask(rt[l-1],rt[r],1,1000000000,1,pos);
if(res>=pos) pos=res+1;
else break;
}
printf("%d\n",pos);
}
int main(){
Init();
int m=read();
while(m--){
int l=read(),r=read();
Work(l,r);
}
}
|
