LG4137

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=2e5+7;
const int S=450;
int n,m;
int a[N];
int be[N];
int cnt[N];
int Ans[N];
int sum[N];

inline void work(int pos,int d){
    if(a[pos]>n)return ;
    if(d==1){
        cnt[a[pos]]++;
        if(cnt[a[pos]]==1)sum[a[pos]/S]++;
    }
    else {
        cnt[a[pos]]--;
        if(cnt[a[pos]]==0)sum[a[pos]/S]--;
    }
}

inline int calc(){
    for(int i=0;i<S;i++){
        if(sum[i]<S){
            for(int j=0;j<S;++j){
                if(!cnt[i*S+j])return i*S+j;
            }
        }
    }
}

struct Query{
    int l,r,id;
    inline bool operator < (const Query &a)const{
        return be[l]==be[a.l]?r<a.r:l<a.l;
    }
}Q[N];

int main(){
    // freopen("forest.in","r",stdin);
    // freopen("forest.out","w",stdout);
    r(n),r(m);
    int size=sqrt(n);
    for(int i=1;i<=n;++i){
        be[i]=(i-1)/size+1;
        r(a[i]);
    }
    for(int i=1;i<=m;++i){
        r(Q[i].l),r(Q[i].r);
        Q[i].id=i;
    }
    sort(Q+1,Q+m+1);
    int l=1,r=0;
    for(int i=1;i<=m;++i){
        Query &x=Q[i];
        while(r>Q[i].r)work(r--,-1);
        while(r<Q[i].r)work(++r,1);
        while(l>Q[i].l)work(--l,1);
        while(l<Q[i].l)work(l++,-1);
        Ans[x.id]=calc();
    }
    for(int i=1;i<=m;++i){
        printf("%d\n",Ans[i]);
    }
}