#include <fstream>
#include <algorithm>
#include <cmath>
#define N 100005
using namespace std;
ifstream fin("median_query.in");
ofstream fout("median_query.out");
struct Elem
{
    int val, poz;
    bool operator <(const Elem &other) const
    { return val<other.val;}
};

Elem nnorm[N];
int rnorm[N];
int vect[N], Lbuck;
struct Query
{
    int l,r, orig;
    bool operator<(const  Query & other) const
    {
        if(l/Lbuck == other.l/Lbuck) return r < other.r;
        return l/Lbuck < other.l/Lbuck;
    }
}queries[N];

int  sol[N];
int n,q;
struct AIB
{
    int v[N];
    void update(int node, int val)
    {
        for(int i=node;i<=n;i+=(i&(-i)))
            v[i]+=val;
    }
    int query(int node)
    {
        int s=0;
        for(int i=node;i>=1;i-=(i&(-i)))
            s+=v[i];
        return s;
    }
    int binar(int val)
    {
        int step=(1<<17);
        int poz=0;
        while(step)
        {
            if(poz+step<=n && v[poz+step]<val)
                val-=v[poz+step],poz+=step;
            step/=2;
        }
        return poz+1;
    }
}aib;
void ADD(int poz)
{
    aib.update(vect[poz],1);
}
void DEL(int poz)
{
    aib.update(vect[poz],-1);
}
int main()
{
    fin>>n>>q;
    Lbuck=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        int x;
        fin>>x;
        nnorm[i].val=x;
        nnorm[i].poz=i;
    }
    sort(nnorm+1,nnorm+n+1);
    for(int i=1;i<=n;i++)
    {
        vect[nnorm[i].poz]=i;
        rnorm[i]=nnorm[i].val;
    }
    for(int i=1;i<=q;++i)
    {
        fin>>queries[i].l>>queries[i].r;
        queries[i].orig=i;
    }
    sort(queries+1, queries+q+1);
    int st=1, dr=0;
    for(int i=1;i<=q;++i)
    {
        int l,r;
        l=queries[i].l;
        r=queries[i].r;
        while(dr<r) ++dr, ADD(dr);
        while(st<l) DEL(st), ++st;

        while(st>l) --st, ADD(st);
        while(dr>r) DEL(dr),--dr;
        int med=(r-l+2)/2;
        sol[queries[i].orig]=rnorm[aib.binar(med)];
    }
    for(int i=1;i<=q;i++)
        fout<<sol[i]<<"\n";
    return 0;
}