#include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define ll long long

 #define il inline

 #define N 500100

 using namespace std;

 //re

 int n,m,tot;

 int a[N],root[N];

 struct Seg{

     int ls,rs,sum;

 }seg[N*];

 int gc()

 {

     int rett=,fh=;char p=getchar();

     while(p<''||p>''){if(p=='-')fh=-;p=getchar();}

     while(p>=''&&p<=''){rett=(rett<<)+(rett<<)+p-'';p=getchar();}

     return rett*fh;

 }

 il void pushup(int rt){seg[rt].sum=seg[seg[rt].ls].sum+seg[seg[rt].rs].sum;}

 void build(int l,int r,int rt)

 {

     if(l==r) return;

     int mid=(l+r)>>;

     seg[rt].ls=++tot,build(l,mid,tot);

     seg[rt].rs=++tot,build(mid+,r,tot);

 }

 void update(int x,int l,int r,int rt1,int rt2,int val)

 {

     if(l==r) {seg[rt2].sum+=val;return;}

     int mid=(l+r)>>;

     if(x<=mid){

         if(!seg[rt2].ls||seg[rt2].ls==seg[rt1].ls){

             seg[rt2].ls=++tot,seg[seg[rt2].ls].sum=seg[seg[rt1].ls].sum;

             if(!seg[rt2].rs) seg[rt2].rs=seg[rt1].rs;

         }update(x,l,mid,seg[rt1].ls,seg[rt2].ls,val);

     }else{

         if(!seg[rt2].rs||seg[rt2].rs==seg[rt1].rs){

             seg[rt2].rs=++tot,seg[seg[rt2].rs].sum=seg[seg[rt1].rs].sum;

             if(!seg[rt2].ls) seg[rt2].ls=seg[rt1].ls;

         }update(x,mid+,r,seg[rt1].rs,seg[rt2].rs,val);

     }pushup(rt2);

 }

 int query(int l,int r,int rt1,int rt2,int len)

 {

     if(l==r) return l;

     int mid=(l+r)>>;

     if(seg[seg[rt2].ls].sum-seg[seg[rt1].ls].sum>=len)

         return query(l,mid,seg[rt1].ls,seg[rt2].ls,len);

     if(seg[seg[rt2].rs].sum-seg[seg[rt1].rs].sum>=len)

         return query(mid+,r,seg[rt1].rs,seg[rt2].rs,len);

     return ;

 }

 int main()

 {

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

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

     for(int i=;i<=n;i++) a[i]=gc();

     root[]=++tot,build(,n,tot);

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

         root[i]=++tot,update(a[i],,n,root[i-],root[i],);

     int x,y;

     while(m--)

     {

         x=gc(),y=gc();

         printf("%d\n",query(,n,root[x-],root[y],(y-x+)/+));

     }

     return ;

 }