#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=200011,SN=511;

template<typename tp>inline void read(tp &kk){

    tp ret=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}

    kk=ret*f;

}

int n,m,bl[N],bs,a[N],mina;

int ar[N];

struct ques

{

    int l,r,id;

    bool operator < (const ques &a)const{return bl[l]==bl[a.l]?r<a.r:bl[l]<bl[a.l];}

    void init(int i){id=i,read(l),read(r);}

}q[N];

struct ShangYang

{

    int l[SN],r[SN],sz,buk[N],bukk[SN],b[N],bb;

    void start()

    {

        sz=ceil(sqrt(mina));

        for(int i=0;i<mina;i+=sz)

        {

            bb++;

            l[bb]=i,r[bb]=min(mina-1,i+sz-1);

            for(int j=l[bb];j<=r[bb];j++) b[j]=bb;

        }

    }

    void add(int x)

    {

        if(x>=mina) return;

        if(!buk[x]) bukk[b[x]]++;

        buk[x]++;

    }

    void mus(int x)

    {

        if(x>=mina) return;

        buk[x]--;

        if(!buk[x]) bukk[b[x]]--;

    }

    int query()

    {

        for(int i=1;i<=bb;i++)

        {

            if(bukk[i]<r[i]-l[i]+1)

            {

                for(int j=l[i];j<=r[i];j++) if(!buk[j]) return j;

            }

        }

        return mina;

    }

    void ot()

    {

        for(int i=0;i<mina;i++) printf("%d ",buk[i]);

        putchar('\n');

        for(int i=1;i<=bb;i++) printf("%d ",bukk[i]);

        putchar('\n');

    }

}sy;

int prt[N];

void icu()

{

    sort(q+1,q+1+m);

    int l=1,r=0;

    for(int i=1;i<=m;i++)

    {

        // printf("%d %d %d\n",q[i].id,q[i].l,q[i].r);

        while(r<q[i].r) sy.add(a[++r]);

        while(l>q[i].l) sy.add(a[--l]);

        while(r>q[i].r) sy.mus(a[r--]);

        while(l<q[i].l) sy.mus(a[l++]);

        // sy.ot();

        prt[q[i].id]=sy.query();

    }

}

int main()

{

    // freopen("testdata.in","r",stdin);

    // freopen("996.out","w",stdout);

    read(n),read(m);

    bs=ceil(sqrt(n));

    for(int i=1;i<=n;i++) read(a[i]),ar[i]=a[i],bl[i]=(i-1)/bs+1;

    sort(ar+1,ar+1+n);

    ar[0]=-1;

    mina=ar[n]+1;

    for(int i=1;i<=n;i++) if(ar[i]-ar[i-1]>1){mina=ar[i-1]+1;break;}

    if(mina==0){for(int i=1;i<=m;i++) puts("0");return 0;}

    for(int i=1;i<=m;i++) q[i].init(i);

    sy.start();

    icu();

    for(int i=1;i<=m;i++) printf("%d\n",prt[i]);

    return 0;

}