#include <bits/stdc++.h>
const int N = 5e5 + 5;
const int M = 5e5 + 1;
int n, q, B, a[N], ans[N];
std::array<int, 3> Q[N];

#define lc (p << 1)
#define rc (p << 1 | 1)
struct SegmentTree 
{
    int mx[N << 2], tag[N << 2];

    void upd(int p) { mx[p] = std::max(mx[lc], mx[rc]); }

    void build(int p, int L, int R)
    {
        if (L == R) return mx[p] = -L, tag[p] = 0, void();
        int mid = (L + R) >> 1;
        build(lc, L, mid), build(rc, mid + 1, R);
        upd(p);
    }

    void pushdown(int p)
    {
        if (tag[p])
        {
            int t = tag[p]; tag[p] = 0;
            mx[lc] += t, mx[rc] += t;
            tag[lc] += t, tag[rc] += t;
        }
    }

    void modify(int p, int L, int R, int l, int r, int x)
    {
        if (l <= L && R <= r) return mx[p] += x, tag[p] += x, void();
        int mid = (L + R) >> 1; pushdown(p);
        if (l <= mid) modify(lc, L, mid, l, r, x);
        if (r >= mid + 1) modify(rc, mid + 1, R, l, r, x);
        upd(p);
    }

    int qry(int p, int L, int R)
    {
        if (L == R) return L;
        int mid = (L + R) >> 1; pushdown(p);
        if (mx[rc] >= 0) return qry(rc, mid + 1, R);
        else return qry(lc, L, mid);
    }
} T;

inline void add(int x)
{
    T.modify(1, 0, M, x + 1, M, 1);
}

inline void del(int x)
{
    T.modify(1, 0, M, x + 1, M, -1);
}

signed main()
{
    // freopen("set3.in", "r", stdin);
    // freopen("tst.out", "w", stdout);
    std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
    std::cin >> n >> q;
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    // for (int i = 401814; i <= 417313; i++) printf("%d ", a[i]);
    // return 0;
    for (int i = 1; i <= q; i++)
    {
        int l, r; std::cin >> l >> r;
        Q[i] = {l, r, i};
    } T.build(1, 0, M);
    B = std::max(1, (int)sqrt(n));
    std::sort(Q + 1, Q + q + 1, [](std::array<int, 3> x, std::array<int, 3> y)
    {
        int posx = x[0] / B, posy = y[0] / B;
        if (posx == posy) return ((posx & 1) ? x[1] < y[1] : x[1] > y[1]);
        return posx < posy;
    });
    int l = 1, r = 0;
    for (int i = 1; i <= q; i++)
    {
        int L = Q[i][0], R = Q[i][1], id = Q[i][2];
        while (l > L) l--, add(a[l]);
        while (r < R) r++, add(a[r]);
        while (l < L) del(a[l]), l++;
        while (r > R) del(a[r]), r--;
        ans[id] = T.qry(1, 0, M);
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    std::cerr << "Time = " << (double)clock() / CLOCKS_PER_SEC << "s" << std::endl;
    return 0;
}