median_query

#include <bits/stdc++.h>
using namespace std;
ifstream fin("median_query.in");
ofstream fout("median_query.out");
struct Cell
{
    int val,poz;
    bool operator < (const Cell &Next) const
    {
        return val < Next.val;
    }
};
Cell VN[100005];
int WVN[100005];
int vec[100005], Buck_size;
struct Query
{
    int l, r, Pozo;
    bool operator < (const Query &Next) const
    {
        if(l / Buck_size == Next.l / Buck_size)
            return r < Next.r;
        return l / Buck_size < Next.l / Buck_size;
    }
} queries[100005];
int ans[100005];
int N, Q;
struct AIB
{
    int v[100005];
    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 CBinary(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(vec[poz],1);
}

void DEL(int poz)
{
    aib.update(vec[poz],-1);
}

int main()
{
    fin>>N>>Q;
    Buck_size=sqrt(N);
    for(int i=1;i<=N;++i)
    {
        int x;
        fin>>x;
        VN[i].val=x;
        VN[i].poz=i;
    }
    sort(VN+1,VN+N+1);
    for(int i=1;i<=N;++i)
    {
        vec[VN[i].poz]=i;
        WVN[i]=VN[i].val;
    }
    for(int i=1;i<=Q;++i)
    {
            fin>>queries[i].l>>queries[i].r;
            queries[i].Pozo=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;
        ans[queries[i].Pozo]=WVN[aib.CBinary(med)];
    }
    for(int i=1;i<=Q;++i)
        fout<<ans[i]<<'\n';
    return 0;
}