/*

    指针

*/

#include <algorithm>

#include <cstdio>

#define Max 2000009

void read (int &now)

{

    now = ;

    register char word = getchar ();

    while (word < '' || word > '')

        word = getchar ();

    while (word >= '' && word <= '')

    {

        now = now *  + word - '';

        word = getchar ();

    }

}

inline int min (int a, int b)

{

    return a < b ? a : b;

}

inline int max (int a, int b)

{

    return a > b ? a : b;

}

struct Segment_Tree_Data

{

    Segment_Tree_Data *Left, *Right;

    int key;

    Segment_Tree_Data ()

    {

        key = ;

        Left = Right = NULL;

    }

};

Segment_Tree_Data *Root[Max];

int N, M;

class Lasting_Segment_Tree_Type

{

    private :

        int Query (Segment_Tree_Data *&Last, Segment_Tree_Data *&now, int l, int r)

        {

            if (l == r)

                return l;

            register int Mid = l + r >> ;

            if (now->Left->key - Last->Left->key > Need)

                return Query (Last->Left, now->Left, l, Mid);

            else if (now->Left->key - Last->Right->key > Need)

                return Query (Last->Right, now->Right, Mid + , r);

            return ;

        }

        int Need;

    public :

        void Build (Segment_Tree_Data *&now, int l, int r)

        {

            now = new Segment_Tree_Data;

            if (l == r)

                return ;

            register int Mid = l + r >> ;

            Build (now->Left, l, Mid);

            Build (now->Right, Mid + , r);

        }

        void Updata (Segment_Tree_Data *Last, Segment_Tree_Data *&now, int pos, int l, int r)

        {

            now = new Segment_Tree_Data;

            now->key = Last->key + ;

            if (l == r)

                return ;

            register int Mid = l + r >> ;

            if (pos <= Mid)

            {

                now->Right = Last->Right;

                Updata (Last->Left, now->Left, pos, l, Mid);

            }

            else

            {

                now->Left = Last->Left;

                Updata (Last->Right, now->Right, pos, Mid + , r);

            }

        }

        int Query_Section (int l, int r)

        {

            Need = r - l +  >> ;

            return Query (Root[l - ], Root[r], , N);

        }

};

Lasting_Segment_Tree_Type Tree;

int rank[Max];

int number[Max];

int main (int argc, char *argv[])

{

    read (N);

    read (M);

    Tree.Build (Root[], , N);

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

    {

        read (number[i]);

        Root[i] = Root[i - ];

        Tree.Updata (Root[i - ], Root[i], number[i], , N);

    }

    for (int x, y; M--; )

    {

        read (x);

        read (y);

        printf ("%d\n", Tree.Query_Section (x, y));

    }

    return ;

}

/*

    luogu P3567 [POI2014]KUR-Couriers

    主席树 + 权值线段树 + 离散化

    每次查询的时候向大于r-l+1 / 2的一边走

    若查不到则返回0     

*/

#include <algorithm>

#include <cstdio>

#define Max 800006

void read (int &now)

{

    now = ;

    register char word = getchar ();

    while (word < '' || word > '')

        word = getchar ();

    while (word >= '' && word <= '')

    {

        now = now *  + word - '';

        word = getchar ();

    }

}

struct Segment_Tree_Date

{

    int Left, Right;

    int key;

};

int Root[Max];

Segment_Tree_Date tree[Max << ];

class Lasting_Segment_Tree_Type

{

    private :

        int Tree_Count;

    public :

        void Build (int &now, int l, int r)

        {

            now = ++Tree_Count;

            if (l == r)

                return ;

            register int Mid = l + r >> ;

            Build (tree[now].Left, l, Mid);

            Build (tree[now].Right, Mid + , r);

        }

        void Updata (int Last, int &now, int l, int r, int pos)

        {

            now = ++Tree_Count;

            tree[now].key = tree[Last].key + ;

            if (l == r)

                return ;

            int Mid = l + r >> ;

            if (pos <= Mid)

            {

                tree[now].Right = tree[Last].Right;

                Updata (tree[Last].Left, tree[now].Left, l, Mid, pos);

            }

            else

            {

                tree[now].Left = tree[Last].Left;

                Updata (tree[Last].Right, tree[now].Right, Mid + , r, pos);

            }

        }

        int Query (int Last, int now, int l, int r, int Need)

        {

            if (l == r)

                return l;

            register int Mid = l + r >> ;

            if (tree[tree[now].Left].key - tree[tree[Last].Left].key > Need)

                return Query (tree[Last].Left, tree[now].Left, l, Mid, Need);

            else if (tree[tree[now].Right].key - tree[tree[Last].Right].key > Need)

                return Query (tree[Last].Right, tree[now].Right, Mid + , r, Need);

            return ;

        }

};

int N, M;

int number[Max];

int rank[Max];

Lasting_Segment_Tree_Type Tree;

int main (int argc, char *argv[])

{

    read (N);

    read (M);

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

    {

        read (number[i]);

        rank[i] = number[i];

    }

    std :: sort (rank + , rank +  + N);

    int Size = std :: unique (rank + , rank +  + N) - rank - ;

    Tree.Build (Root[], , Size);

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

    {

        number[i] = std :: lower_bound (rank + , rank +  + Size, number[i]) - rank;

        Tree.Updata (Root[i - ], Root[i], , Size, number[i]);

    }

    for (int x, y; M--; )

    {

        read (x);

        read (y);

        printf ("%d\n", rank[Tree.Query (Root[x - ], Root[y], , Size, y - x +  >> )]);

    }

    return ;

}