#include <bits/stdc++.h>

using namespace std;

inline int read() {
    int s = 0, w = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-')
            w = -w;
        c = getchar();
    }
    while (isdigit(c)) {
        s = s * 10 + c - 48;
        c = getchar();
    }
    return s * w;
}

const int maxN = 2e5 + 7;

int n, m;

int a[maxN];

int len, pos[maxN], L[330];
bool _c[maxN];
int c[maxN];

struct ques {
    int l, r;
    int id;
    friend bool operator < (ques A, ques B) {
        return pos[A.l] == pos[B.l] ? A.r > B.r : A.l < B.l;
    }
} q[maxN];
int ans[maxN];

inline int del(int x, int A) {
    --c[a[x]];
    if (!c[a[x]])
        A = min(A, a[x]);
    return A;
}

int main() {
    // freopen("P4137_7.in", "r", stdin);
    // freopen("1.out", "w", stdout);

    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();

    memset(L, 0x3f, sizeof(L));
    len = sqrt(n);
    for (int i = 1; i <= n; ++i) {
        pos[i] = (i - 1) / len + 1;
        L[pos[i]] = min(L[pos[i]], i);
    }

    for (int i = 1; i <= m; ++i)
        q[i].l = read(), q[i].r = read(), q[i].id = i;
    sort(q + 1, q + m + 1);

    int l = 1, r = 0, last_block = -1;
    int res = 0;
    for (int i = 1; i <= m; ++i) {
        if (pos[q[i].l] == pos[q[i].r]) {
            int tmp = 0;
            // for (int j = q[i].l; j <= q[i].r; ++j)
            //     _c[a[j]] = true;
            // while (_c[tmp])
            //     tmp++;
            for (int j = q[i].l; j <= q[i].r; ++j)
                if (!_c[a[j]] && (_c[a[j]] = true) && tmp == a[j])
                    while (_c[tmp])
                        tmp++;
            ans[q[i].id] = tmp;
            for (int j = q[i].l; j <= q[i].r; ++j)
                _c[a[j]] = false;
            continue;
        }
        if (pos[q[i].l] != last_block) {
            while (r < n)
                c[a[++r]]++;
            while (l < L[pos[q[i].l]])
                del(l++, 0);
            res = 0;
            while (c[res])
                res++;
            last_block = pos[q[i].l];
        }
        while (r > q[i].r)
            res = del(r--, res);
        int tmp = res, _l = l;
        while (_l < q[i].l)
            tmp = del(_l++, tmp);
        ans[q[i].id] = tmp;

        while (_l > l)
            c[a[--_l]]++;
    }

    for (int i = 1; i <= m; ++i)
        cout << ans[i] << '\n';

    return 0;
}