#include <set>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 500005;

int n, m, a[N], c[N], ans[N];
vector <int> p[N];

struct Query
{
    int l, r, id;
};
Query q[N];

struct SegmentTree
{
    struct Node
    {
        int Max, pos;
    };
    struct Tree
    {
        int l, r, Max, pos, add;
    };
    Tree s[N << 2];

    #define ls p << 1
    #define rs p << 1 | 1

    void build(int p, int l, int r)
    {
        s[p].l = l;
        s[p].r = r;
        s[p].pos = l;
        if(l == r)
            return;
        int mid = l + r >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
    }

    void push_down(int p)
    {
        s[ls].add += s[p].add;
        s[ls].Max += s[p].add;
        s[rs].add += s[p].add;
        s[rs].Max += s[p].add;
        s[p].add = 0;
    }

    void push_up(int p)
    {
        s[p].Max = max(s[ls].Max, s[rs].Max);
        if(s[ls].Max >= s[rs].Max)
            s[p].pos = s[ls].pos;
        else
            s[p].pos = s[rs].pos;
    }

    void Add(int p, int l, int r, int k)
    {
        if(s[p].l >= l && s[p].r <= r)
        {
            s[p].add += k;
            s[p].Max += k;
            return;
        }
        push_down(p);
        int mid = s[p].l + s[p].r >> 1;
        if(l <= mid)
            Add(ls, l, r, k);
        if(r > mid)
            Add(rs, l, r, k);
        push_up(p);
    }

    void Upd(int p, int x, int k)
    {
        if(s[p].l == s[p].r)
        {
            s[p].Max = k;
            return;
        }
        push_down(p);
        int mid = s[p].l + s[p].r >> 1;
        if(x <= mid)
            Upd(ls, x, k);
        else
            Upd(rs, x, k);
        push_up(p);
    }

    Node maxNode(Node x, Node y)
    {
        if(x.Max >= y.Max)
            return x;
        return y;
    }

    Node Get(int p, int l, int r)
    {
        if(s[p].l >= l && s[p].r <= r)
            return (Node){s[p].Max, s[p].pos};
        push_down(p);
        int mid = s[p].l + s[p].r >> 1;
        if(r <= mid)
            return Get(ls, l, r);
        if(l > mid)
            return Get(rs, l, r);
        return maxNode(Get(ls, l, r), Get(rs, l, r));
    }
};
SegmentTree S, T;

set < pair<int, int> > lpos, rpos;

void add(int x, int k)
{
    for(; x <= n; x += x & -x)
        c[x] += k;
}

int get(int x)
{
    int r = 0;
    for(; x; x -= x & -x)
        r += c[x];
    return r;
}

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

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i)
        scanf("%d", &a[i]), p[a[i]].push_back(i), add(i, 1);
    for(int i = 1; i <= m; ++ i)
        scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;

    sort(q + 1, q + 1 + m, [](Query i, Query j)
        { return i.l == j.l ? i.r > j.r : i.l < j.l;});

    T.build(1, 1, m);
    S.build(1, 1, m);
    for(int i = 1, R = 0; i <= m; ++ i)
    {
        if(q[i].l == q[i - 1].l || q[i].r <= R)
        {
            S.Upd(1, i, q[i].r);
            T.Upd(1, i, -1e9);
        }
        else
        {
            R = q[i].r;
            T.Upd(1, i, q[i].r - q[i].l + 1);
            lpos.insert(make_pair(q[i].l, i));
            rpos.insert(make_pair(q[i].r, i));
        }    
    }

    for(int i = n; i >= 0; -- i)
    {
        for(int u : p[i])
        {
            add(u, -1);
            auto itl = lpos.upper_bound(make_pair(u, N));
            auto itr = rpos.lower_bound(make_pair(u, 0));
            // printf("{%d, %d}, {%d, %d}\n", itl -> first, itl -> second, itr -> first, itr -> second);
            if(itl != lpos.begin() && itr != rpos.end() && prev(itl) -> second >= itr -> second)
                T.Add(1, itr -> second, prev(itl) -> second, -1);
        }
        while(T.s[1].Max >= i)
        {
            int u = T.s[1].pos, r, R;
            ans[q[u].id] = i;
            lpos.erase(make_pair(q[u].l, u));
            rpos.erase(make_pair(q[u].r, u));
            if(lpos.size() == 0)
            {
                r = m;
                R = 0;
            }
            else
            {
                auto itr = lpos.upper_bound(make_pair(q[u].l, u));
                r = (itr == lpos.end() ? m : itr -> second);
                R = (itr == lpos.begin() ? 0 : prev(itr) -> first);
                if(itr == lpos.end() && prev(itr) -> second == u)
                    R = 0;
            }

            if(u + 1 <= r)
            {
                SegmentTree::Node x = S.Get(1, u + 1, r);
                while(u + 1 <= r && x.Max > 0 && q[x.pos].r > R)
                {
                    r = x.pos - 1;
                    lpos.insert(make_pair(q[x.pos].l, x.pos));
                    rpos.insert(make_pair(q[x.pos].r, x.pos));
                    S.Upd(1, x.pos, 0);
                    T.Upd(1, x.pos, get(q[x.pos].r) - get(q[x.pos].l - 1));
                    if(u + 1 <= r)
                        x = S.Get(1, u + 1, r);
                }
            }
            T.Upd(1, u, -1e9);
        }
    }

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

    return 0;
}