/*

  借此写一写对于主席树的认识。

  我们在做数据结构题目的过程中可能会用到多次更新前的某一个状态，所以我们要想一个办法储存下每一个时刻的树。

  暴力做n棵树？这样的时间和空间都会华丽的GG。

  我们会发现对于一个状态，相对于他前一个状态的改变是很少的，那是不是意味着可以多加几个点就可以，而不是暴力建一棵新树。

  答案是肯定的。我们再加点的过程中只要利用前一棵树的信息和新状态的信息，在创立几个新点就行了。 

  PS：我在一个问题上搞了好几个小时，关于新树的大小和原来的树是否相同的问题，貌似很明显是相同的，然而我傻，以为不相同，导致mengbi了很长时间。

*/

#include<cstdio>

#include<iostream>

#define N 500010

using namespace std;

int root[N],ls[N*],rs[N*],sum[N*],cnt,n,m;

void add(int pre,int &k,int l,int r,int v){

    k=++cnt;

    sum[k]=sum[pre]+;

    if(l==r) return;

    ls[k]=ls[pre];rs[k]=rs[pre];

    int mid=l+r>>;

    if(v<=mid) add(ls[pre],ls[k],l,mid,v);

    else add(rs[pre],rs[k],mid+,r,v);

}

int query(int x,int y){//两个时刻

    int l=,r=n,tmp=(y-x+)/;

    x=root[x-];y=root[y];

    while(l!=r){

        if(sum[y]-sum[x]<=tmp)return ;

        int mid=l+r>>;

        if(sum[ls[y]]-sum[ls[x]]>tmp){

            r=mid;x=ls[x];y=ls[y];

        }

        else if(sum[rs[y]]-sum[rs[x]]>tmp){

            l=mid+;x=rs[x];y=rs[y];

        }

        else return ;

    }

    return l;

}

int main(){

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

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

        int x;scanf("%d",&x);

        add(root[i-],root[i],,n,x);

    }

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

        int x,y;scanf("%d%d",&x,&y);

        printf("%d\n",query(x,y));

    }

    return ;

}