#include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #include <map>

 #include <cmath>

 using namespace std;

 const int Maxn=;

 struct Info{int l,r,Id;}P[Maxn];

 int a[Maxn],U[Maxn],Pos[Maxn],Belong[Maxn],Num[Maxn],L[Maxn],R[Maxn],Ans[Maxn];

 int n,m,Block,tot;

 inline bool cmp(Info A,Info B)

 {

     if (Pos[A.l]!=Pos[B.l]) return Pos[A.l]<Pos[B.l];

     return A.r<B.r;

 }

 inline void Add(int x)

 {

     if (x>n) return;

     if (U[x]==) Num[Belong[x]]++;

     U[x]++;

 }

 inline void Del(int x)

 {

     if (x>n) return;

     U[x]--;

     if (U[x]==) Num[Belong[x]]--;

 }

 inline  int Query()

 {

     int i; for (i=;i<=tot;i++) if (Num[i]!=Block) break;

     for (int j=L[i];j<=R[i];j++)  if (!U[j]) return j;

 }

 int main()

 {

     scanf("%d%d",&n,&m); Block=(int)sqrt(n); tot=n/Block+;

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

     {

         Belong[i]=i/Block+;

         if (!L[Belong[i]]) L[Belong[i]]=i;

         R[Belong[i]]=i;

     }L[]=;

     for (int i=;i<=n;i++) Pos[i]=i/Block+;

     for (int i=;i<=n;i++) scanf("%d",&a[i]);

     for (int i=;i<=m;i++) scanf("%d%d",&P[i].l,&P[i].r),P[i].Id=i;

     sort(P+,P+m+,cmp); int l=,r=;

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

     {

         while (r<P[i].r) Add(a[++r]);

         while (l<P[i].l) Del(a[l++]);

         while (l>P[i].l) Add(a[--l]);

         while (r>P[i].r) Del(a[r--]);

         Ans[P[i].Id]=Query();

     }

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

     return ;

 }