/**************************************************************

     Problem: 3524

     User: Tunix

     Language: C++

     Result: Accepted

     Time:5752 ms

     Memory:120416 kb

 ****************************************************************/

 //BZOJ 3524

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*=sign;

 }

 /*******************tamplate********************/

 const int N=;

 struct Tree{

     int cnt,l,r;

 }t[N*];

 int root[N],n,m,cnt;

 #define mid (l+r>>1)

 void update(int &o,int l,int r,int pos){

     t[++cnt]=t[o]; o=cnt; ++t[o].cnt;

     if (l==r) return;

     if (pos<=mid) update(t[o].l,l,mid,pos);

     else update(t[o].r,mid+,r,pos);

 }

 int query(int i,int j,int num){

     i=root[i],j=root[j];

     int l=,r=n;

     while(l!=r){

         if (t[t[j].l].cnt-t[t[i].l].cnt>num)

             r=mid,j=t[j].l,i=t[i].l;

         else if (t[t[j].r].cnt-t[t[i].r].cnt>num)

             l=mid+,j=t[j].r,i=t[i].r;

         else return ;

     }

     return l;

 }

 #undef mid

 int main(){

     n=getint(),m=getint();

     F(i,,n){

         root[i]=root[i-];

         update(root[i],,n,getint());

     }

     F(i,,m){

         int l=getint(),r=getint();

         printf("%d\n",query(l-,r,(r-l+)>>));

     }

     return ;

 }