rt. $88~\text{pts}$，最后一个点挂了，前 $160$ 行为快读。

#include <bits/stdc++.h>

#define lop(n, s, e) for (int n = (s); n <= (e); ++n)
#define ril(n, s, e) for (int n = (s); n >= (e); --n)
#define nem(n, c) while (!n.empty() && (c))

namespace IO
{
    namespace Fast
    {
        namespace Read
        {
            const size_t BUFSIZE = 1 << 20;
            char buf[BUFSIZE], *s = buf, *e = buf;

            inline char getchar()
            {
                if (s == e)
                    e = (s = buf) + fread(buf, 1, BUFSIZE, stdin);
                return s == e ? EOF : *s++;
            }
        }
        namespace Write
        {
            const size_t BUFSIZE = 1 << 20;
            char buf[BUFSIZE], *s = buf, *e = buf + BUFSIZE;

            inline void flush()
            {
                fwrite(buf, 1, s - buf, stdout);
                s = buf;
            }

            inline void putchar(const char &c)
            {
                *s++ = c;
                if (s == e)
                    flush();
            }
        }
    }
    using Fast::Read::getchar;
    using Fast::Write::flush;
    using Fast::Write::putchar;

    template <class T>
    inline T &read(T &x)
    {
        x = 0;
        char f = 1;
        char ch = getchar();
        for (; !isdigit(ch); ch = getchar())
            if (!(ch ^ 45))
                f = -1;
        for (; isdigit(ch); ch = getchar())
            x = (x << 3) + (x << 1) + (ch ^ 48);
        x *= f;
        return x;
    }

    template <class First, class... Args>
    inline void read(First &first, Args &...args)
    {
        read(first);
        read(args...);
    }

    template <class T>
    inline T &readReal(T &x)
    {
        x = 0.0;
        T f = 1.0;
        char ch = getchar();
        for (; !isdigit(ch); ch = getchar())
            if (!(ch ^ 45))
                f = -1.0;
        for (; isdigit(ch); ch = getchar())
            x = x * 10.0 + static_cast<T>(ch ^ 48);
        if (ch == '.')
        {
            T b = 0.1;
            for (ch = getchar(); isdigit(ch); ch = getchar())
                x += b * static_cast<T>(ch ^ 48), b *= 0.1;
        }
        x *= f;
        return x;
    }

    template <class First, class... Args>
    inline void readReal(First &first, Args &...args)
    {
        readReal(first);
        readReal(args...);
    }

    template <class T>
    inline void write(T x)
    {
        static char tmp[155], top;
        if (x < 0)
            putchar(45), x = -x;
        if (x == 0)
        {
            putchar(48);
            return;
        }
        top = 0;
        while (x)
            tmp[top++] = x % 10 ^ 48, x /= 10;
        while (top--)
            putchar(tmp[top]);
    }

    template <class T>
    inline void writeReal(T x, T eps = 1e-11, int prec = 9999)
    {
        typedef __int128 FINT;
        static FINT i, l;
        static T f, b;
        static char c;
        if (x < 0.0)
            putchar(45), x = -x;
        i = x;
        f = x - i;
        write(i);
        if (std::abs(f) <= eps)
            return;
        putchar(46);
        b = 0.1;
        l = 0;
        while (std::abs(f) > eps && l < prec)
            c = floor(f / b), f -= b * c, putchar(c ^ 48), b *= 0.1, l++;
    }

    template <class T>
    inline void writeReal(T x, int prec)
    {
        writeReal(x, static_cast<T>(0), prec);
    }

    inline void endl() { putchar(10); }

    inline void space() { putchar(32); }

    inline void tab() { putchar(9); }

#define endl endl()
#define space space()
#define tab tab()
}
using namespace IO;
using namespace std;

template <class T>
using minheap = priority_queue<T, vector<T>, greater<>>;
template <class T>
using maxheap = priority_queue<T, vector<T>, less<>>;
int now;
int mp[10000000];
int a[10000000];
int q1[10000000];
int q2[10000000];
int belong[10000000];
struct edge
{
    int l, r, id;
} q[1000000];
int ans[10000000];
void add(int pos)
{
    ++mp[a[pos]];
    int pos1 = pos;
    while (mp[now] >= 1)
    {
        ++now;
    }
}
void del(int pos)
{
    --mp[a[pos]];
    while (now > 0 && mp[now - 1] == 0)
        --now;
    if (mp[a[pos]] == 0)
        now = min(now, a[pos]);
}
int cmp(edge a, edge b)
{
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
int main()
{
    int n, q1;
    read(n, q1);
    int size = pow(n + 2, 0.5);
    int bnum = ceil((double)n / size);
    for (int i = 1; i <= bnum; ++i)
        for (int j = (i - 1) * size + 1; j <= i * size; ++j)
        {
            belong[j] = i;
        }
    int l = 1;
    int r = 0;
    for (int i = 1; i <= n; i++)
        read(a[i]);
    for (int i = 1; i <= q1; i++)
        read(q[i].l, q[i].r), q[i].id = i;
    sort(q + 1, q + q1 + 1, cmp);
    for (int i = 1; i <= q1; i++)
    {
        int ql = q[i].l;
        int qr = q[i].r;
        while (l < ql)
            del(l++);
        while (l > ql)
            add(--l);
        while (r < qr)
            add(++r);
        while (r > qr)
            del(r--);
        ans[q[i].id] = now;
    }
    for (int i = 1; i <= q1; i++)
    {
        write(ans[i]);
        endl;
    }
    flush();
}