#include<bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + ;

struct query

{

        int l , r;

        int id;

} q[MAXN];

int n , m , idx;

int a[MAXN] , lson[MAXN << ] , rson[MAXN << ] , sum[MAXN << ] , root[MAXN] , tmp[MAXN] , ans[MAXN];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline bool cmp(query a , query b)

{

        return a.r < b.r;

}

inline void build(int &k , int l , int r)

{

        k = ++idx;

        if (l == r) return;

        int mid = (l + r) >> ;

        build(lson[k] , l , mid);

        build(rson[k] , mid +  , r);

}

inline void modify(int &k , int old , int l , int r , int pos , int value)

{

        k = ++idx;

        lson[k] = lson[old] , rson[k] = rson[old];

        sum[k] = sum[old] + value;

        if (l == r) return;

        int mid = (l + r) >> ;

        if (mid >= pos) modify(lson[k] , lson[k] , l , mid , pos , value);

        else modify(rson[k] , rson[k] , mid +  , r , pos , value);

}

inline int query(int rt1 , int rt2 , int l , int r , int x)

{

        if (l == r) return l;

        int mid = (l + r) >> ;

        if (sum[lson[rt1]] - sum[lson[rt2]] > x) return query(lson[rt1] , lson[rt2] , l , mid , x);

        else if (sum[rson[rt1]] - sum[rson[rt2]] > x) return query(rson[rt1] , rson[rt2] , mid +  , r , x);

        else return ;

} 

int main()

{

        read(n); read(m);

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

        {

                read(a[i]);

                tmp[i] = a[i];

        }

        sort(tmp +  , tmp + n + );

        int len = unique(tmp +  , tmp + n + ) - tmp - ;

        for (int i = ; i <= n; i++) a[i] = lower_bound(tmp +  , tmp + len +  , a[i]) - tmp;

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

        {

                read(q[i].l);

                read(q[i].r);

                q[i].id = i;

        }

        sort(q +  , q + m +  , cmp);

        build(root[] ,  , len);

        int now = ;

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

        {

                modify(root[i] , root[i - ] ,  , n , a[i] , );

                while (now <= m && q[now].r == i) ans[q[now].id] = tmp[query(root[i] , root[q[now].l - ] ,  , n , (q[now].r - q[now].l + ) / )] , ++now;

        }

        for (int i = ; i <= m; i++) printf("%d\n" , ans[i]);

        return ;

}