#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define N 200002

#define BN 452

int n,m,num[N],a[N],l[BN],size[BN],anss[N],b[N],sumv[BN];

struct ASK{int l,r,p;}Q[N];

bool operator < (const ASK &a,const ASK &b)

{return num[a.l]!=num[b.l]?num[a.l]<num[b.l]:a.r<b.r;}

void Insert(const int &x){if(x<=n){if(!b[x])++sumv[num[x]];++b[x];}}

void Delete(const int &x){if(x<=n){--b[x];if(!b[x])--sumv[num[x]];}}

int Query(){for(int i=1;;++i) if(sumv[i]<size[i]) for(int j=l[i];;++j) if(!b[j]) return j;}

int main()

{

	scanf("%d%d",&n,&m);

	int sz=sqrt(n),blo=0; if(!sz) sz=1;

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

	  {

	  	scanf("%d",&a[i]);

	  	if(i%sz==1||sz==1) l[++blo]=i;

	  	num[i]=blo; ++size[blo];

	  }

	l[1]=0; num[0]=1; ++size[1];

	for(int i=1;i<=m;++i) {scanf("%d%d",&Q[i].l,&Q[i].r); Q[i].p=i;}

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

    for(int i=Q[1].l;i<=Q[1].r;++i) Insert(a[i]);

    anss[Q[1].p]=Query();

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

      {

        if(Q[i].l<Q[i-1].l) for(int j=Q[i-1].l-1;j>=Q[i].l;--j) Insert(a[j]);

        else for(int j=Q[i-1].l;j<Q[i].l;++j) Delete(a[j]);

        if(Q[i].r<Q[i-1].r) for(int j=Q[i-1].r;j>Q[i].r;--j) Delete(a[j]);

        else for(int j=Q[i-1].r+1;j<=Q[i].r;++j) Insert(a[j]);

        anss[Q[i].p]=Query();

      }

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

	return 0;

}