两题本质是一样，只不过3585要离散化
这种不修改，不强制的问题，显然先考虑离线算法
这道题的思路和bzoj1878非常像
考虑到如果只是求每个前缀的mex，我们是很容易扫一遍就得出来的
我们设为这个位置的mex
考虑从左往右依次删除当前数会对后面产生什么影响
我们设删除数a[i],a[i]下一个相同数的位置为next[a[i]]
显然对于[i+1,next[a[i]]-1]这些位置的mex可能有影响（如过没有next，就说明对后面所有位置都可能有影响）;
凡是大于a[i]的一律都变成了a[i]
因此我们考虑对每个询问按左端点排序
然后从左往右依次删除a[i](按上述对后面位置进行修改)
不难发现，当某个询问左端点=当前位置i时(当然是先查询后删除了），这个询问的答案就是右端点上的mex，
显然修改操作我们可以用线段树来维护，这样就解决了这个问题
const inf=;
var loc,ans,next,last,sg,p,q,c,a,b:array[..] of longint;
tree:array[..] of longint;
d:array[..] of longint;
v:array[..] of boolean;
i,n,m,j,t,k:longint; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function find(x:longint):longint;
var l,r,m:longint;
begin
l:=;
r:=t;
while l<=r do
begin
m:=(l+r) shr ;
if d[m]=x then exit(m);
if d[m]>x then r:=m- else l:=m+;
end;
end; procedure sort1(l,r:longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=p[(l+r) div ];
repeat
while p[i]<x do inc(i);
while x<p[j] do dec(j);
if not(i>j) then
begin
swap(p[i],p[j]);
swap(q[i],q[j]);
swap(c[i],c[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort1(l,j);
if i<r then sort1(i,r);
end; procedure sort2(l,r:longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=b[(l+r) div ];
repeat
while b[i]<x do inc(i);
while x<b[j] do dec(j);
if not(i>j) then
begin
swap(b[i],b[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort2(l,j);
if i<r then sort2(i,r);
end; procedure build(i,l,r:longint);
var m:longint;
begin
if l=r then
tree[i]:=sg[l]
else begin
tree[i]:=inf;
m:=(l+r) shr ;
build(i*,l,m);
build(i*+,m+,r);
end;
end; procedure push(i:longint);
begin
tree[i*]:=min(tree[i*],tree[i]);
tree[i*+]:=min(tree[i*+],tree[i]);
tree[i]:=inf;
end; procedure work(i,l,r,x,y,z:longint);
var m:longint;
begin
if (x<=l) and (y>=r) then
tree[i]:=min(tree[i],z)
else begin
if tree[i]<>inf then push(i);
m:=(l+r) shr ;
if x<=m then work(i*,l,m,x,y,z);
if y>m then work(i*+,m+,r,x,y,z);
end;
end; function ask(i,l,r,x:longint):longint;
var m:longint;
begin
if l=r then exit(tree[i])
else begin
if tree[i]<>inf then push(i);
m:=(l+r) shr ;
if x<=m then exit(ask(i*,l,m,x))
else exit(ask(i*+,m+,r,x));
end;
end; begin
readln(n,m);
for i:= to n do
begin
read(a[i]);
b[i]:=a[i];
end;
sort2(,n);
if b[]<> then
begin
inc(t);
d[]:=;
end;
inc(t);
d[t]:=b[];
for i:= to n do
begin
if b[i]=b[i-] then continue;
if b[i]-b[i-]> then
begin
inc(t);
d[t]:=b[i-]+;
end;
inc(t);
d[t]:=b[i];
end;
inc(t);
d[t]:=b[n]+;
k:=;
for i:= to n do
begin
loc[i]:=find(a[i]);
v[loc[i]]:=true;
while v[k] do inc(k);
sg[i]:=k;
end;
fillchar(last,sizeof(last),);
fillchar(next,sizeof(next),);
for i:=n downto do
begin
next[i]:=last[loc[i]];
last[loc[i]]:=i;
end; build(,,n);
for i:= to m do
begin
readln(p[i],q[i]);
c[i]:=i;
end; sort1(,m);
j:=;
for i:= to n do
begin
while p[j]=i do
begin
ans[c[j]]:=ask(,,n,q[j]);
inc(j);
end;
if next[i]=- then next[i]:=n+;
work(,,n,i+,next[i]-,loc[i]);
end;
for i:= to m do
writeln(d[ans[i]]);
end.