#include<bits/stdc++.h>
#define int long long
#define L p << 1
#define R p << 1 | 1
#define mid ((l + r) >> 1)
#define fi first
#define se second
#define MULT_TEST 0
using namespace std;
typedef long double ldb;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f3f3f;
const int MOD = 998244353;
const int N = 500005, B = 250;
vector<array<int, 3>> D;
int ans[N], a[N], cnt[N];
inline int read() {
    int w = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        w = (w << 1) + (w << 3) + ch - 48;
        ch = getchar();
    }
    return w * f;
}
struct Seg {
    struct node {
        int mx, tag;
    } tr[N << 2];
    inline void Update(int p, int d) {
        tr[p].tag += d, tr[p].mx += d;
    }
    inline void Pushup(int p) {
        tr[p].mx = max(tr[L].mx, tr[R].mx);
    }
    inline void Pushdown(int p) {
        if (tr[p].tag) {
            Update(L, tr[p].tag), Update(R, tr[p].tag);
            tr[p].tag = 0;
        }
    }
    inline void Build(int p, int l, int r) {
        if (l == r) return tr[p].mx = -INF, void();
        Build(L, l, mid), Build(R, mid + 1, r);
        Pushup(p);
    }
    inline void Modify(int p, int l, int r, int ql, int qr, int d) {
        if (ql > qr) return ;
        if (ql <= l && r <= qr) return Update(p, d), void();
        Pushdown(p);
        if (ql <= mid) Modify(L, l, mid, ql, qr, d);
        if (qr > mid) Modify(R, mid + 1, r, ql, qr, d);
        Pushup(p);
    }
    inline int Query(int p, int l, int r) {
        if (l == r) return tr[p].mx >= 0 ? tr[p].mx + l : -1ll;
        Pushdown(p);
        if (tr[R].mx < 0) return Query(L, l, mid);
        else return Query(R, mid + 1, r);
    }
} A;
inline void Add(int t) {
    if (cnt[a[t]]++ == 0) A.Modify(1, 0, N - 5, a[t], a[t], INF - a[t] - 1);
    A.Modify(1, 0, N - 5, a[t], N - 5, 1);
}
inline void Del(int t) {
    if (--cnt[a[t]] == 0) A.Modify(1, 0, N - 5, a[t], a[t], a[t] + 1 - INF);
    A.Modify(1, 0, N - 5, a[t], N - 5, -1);
}
inline void Solve() {
    int n, q;
    n = read(), q = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= q; i++) {
        int l = read(), r = read();
        D.push_back({l, r, i});
    }
    A.Build(1, 0, N - 5);
    auto cmp = [&](array<int, 3> x, array<int, 3> y) {
        int block = x[0] / B;
        if (block != y[0] / B) return block < y[0] / B;
        else return (block & 1 ? x[1] < y[1] : x[1] > y[1]);
    };
    sort(D.begin(), D.end(), cmp);
    for (int i = 0, l = 1, r = 0; i < q; i++) {
        while (l > D[i][0]) Add(--l);
        while (r < D[i][1]) Add(++r);
        while (l < D[i][0]) Del(l++);
        while (r > D[i][1]) Del(r--);
        ans[D[i][2]] = A.Query(1, 0, N - 5);
    }
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i] + 1);
}
signed main() {
    int _ = 1;
#if MULT_TEST
    _ = read();
#endif 
    while (_--) Solve();
    return 0;
}
/*
3 3
0 0 2
1 3
2 3
3 3
*/