#include<bits/stdc++.h>
using namespace std;
const int N=200050;
int n,m,a[N],ans[N],cnt[N],res,block[N];
struct node{
    int l,r,id;
}q[N];
bool cmp(node a,node b){
    return block[a.l]^block[b.l]?block[a.l]<block[b.l]:(block[a.l]&1)?a.r<b.r:a.r>b.r;
}
inline void add(int x){
    if(a[x]>n)return;
    if(++cnt[a[x]]==1&&a[x]==res)
		while(cnt[res])res++;
}
inline void del(int x){
    if(a[x]>n)return;
    if(--cnt[a[x]]==0&&a[x]<res) res=a[x];
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    cin>>n>>m;
    int sz=sqrt(n)+1;
    for(int i=1;i<=n;i++) cin>>a[i],block[i]=(i-1)/sz+1;
    for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;res=0;
    for(int i=1;i<=m;i++){
        while(l>q[i].l)add(--l);
        while(r<q[i].r)add(++r);
        while(l<q[i].l)del(l++);
        while(r>q[i].r)del(r--);
        ans[q[i].id]=res;
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}