思路：
考虑离线处理
显然 l固定时 r越大 ans越大
那我们不妨按照l从小到大排序
l->l+1的时候 l到next[l]这段区间都跟a[l]取min就好了
搞颗线段树维护一下
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 222222
#define inf 0x3f3f3f3f
int n,q,ans,now,a[N],fst[N],last[N],next[N],vis[N],tree[N*20],Ans[N];
struct Ask{int l,r,id;}ask[N];
bool cmp(Ask a,Ask b){return a.l<b.l;}
void build(int l,int r,int pos){
if(l==r){tree[pos]=fst[l];return;}
int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
build(l,mid,lson),build(mid+1,r,rson);
tree[pos]=inf;
}
void insert(int l,int r,int pos,int L,int R,int Wei){
if(l>=L&&r<=R){tree[pos]=min(tree[pos],Wei);return;}
int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
if(mid<L)insert(mid+1,r,rson,L,R,Wei);
else if(mid>=R)insert(l,mid,lson,L,R,Wei);
else insert(l,mid,lson,L,R,Wei),insert(mid+1,r,rson,L,R,Wei);
}
int query(int l,int r,int pos,int num){
if(l==r)return tree[pos];
int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
if(tree[pos]!=inf)tree[lson]=min(tree[lson],tree[pos]),tree[rson]=min(tree[rson],tree[pos]),tree[pos]=inf;
if(mid<num)return query(mid+1,r,rson,num);
else return query(l,mid,lson,num);
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
vis[a[i]]=1;
while(vis[ans])ans++;
fst[i]=ans;
}
for(int i=n;i;i--)next[i]=last[a[i]]?last[a[i]]:n+1,last[a[i]]=i;
build(1,n,1);
for(int i=1;i<=q;i++)scanf("%d%d",&ask[i].l,&ask[i].r),ask[i].id=i;
sort(ask+1,ask+1+q,cmp),now=1;
for(int i=1;i<=q;i++){
while(now<ask[i].l)insert(1,n,1,now,next[now]-1,a[now]),now++;
Ans[ask[i].id]=query(1,n,1,ask[i].r);
}
for(int i=1;i<=q;i++)printf("%d
",Ans[i]);
}