#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int size,lt,rt;}a[maxn*];

int n,m,x,y,z,sz,ans;

int root[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void build(int &x,int l,int r,int cx)

{

    a[++sz]=a[x];a[sz].size++;x=sz;

    if(l==r)return;

    int mid=(l+r)>>;

    if(cx<=mid)build(a[x].lt,l,mid,cx);

    else build(a[x].rt,mid+,r,cx);

}

int query(int x,int y,int l,int r,int cx)

{

    if(l==r)return l;

    int mid=(l+r)>>;

    if(a[a[y].lt].size-a[a[x].lt].size>=cx)return query(a[x].lt,a[y].lt,l,mid,cx);

    else if(a[a[y].rt].size-a[a[x].rt].size>=cx)return query(a[x].rt,a[y].rt,mid+,r,cx);

    else return ;

}

int main()

{

    read(n);read(m);

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

    {

        read(x);

        root[i]=root[i-];

        build(root[i],,n,x);

    }

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

    {

        read(x);read(y);

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

    }

    return ;

}