#include<bits/stdc++.h>
using namespace std;
set<int>s;
int num[200010];
int n,m;
int a[200010];
int len;
struct node{
    int l,r,id;
}Q[200010];
int ans[200010];
bool cmp(node i,node j){
    int ki=(i.l-1)/len+1,kj=(j.l-1)/len+1;
    if(ki!=kj)return ki<kj;
    return i.r<j.r;
}
int L=1,R=0;
void add(int x){
    if(!num[a[x]]){
        s.erase(a[x]);
    }
    num[a[x]]++;
}
void del(int x){
    num[a[x]]--;
    if(!num[a[x]]){
        s.insert(a[x]);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=0;i<=2e5+1;i++){
        s.insert(i);
    }
    len=3.5*sqrt(n);
    for(int i=1;i<=m;i++){
        cin>>Q[i].l>>Q[i].r;
        Q[i].id=i;
    }
    sort(Q+1,Q+m+1,cmp);
    for(int i=1;i<=m;i++){
        while(R<Q[i].r)R++,add(R);
        while(L<Q[i].l)del(L),L++;
        while(L>Q[i].l)L--,add(L);
        while(R>Q[i].r)del(R),R--;
        ans[Q[i].id]=*s.begin();
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}