如题，只有63分

#include <bits/stdc++.h>
#define file(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
using namespace std;
#define gc getchar
inline int read()
{
    int x = 0, f = 1;
    char ch = gc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = gc();
    }
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    return x * f;
}
const int N = 2e5 + 5;
struct Node
{
    int lps;
    Node *ls, *rs;
    void pushup() { this->lps = min(this->ls->lps, this->rs->lps); }
    Node() { lps = 0, ls = rs = nullptr; };
    Node(Node *ptr) { *this = *ptr; }
    Node(int l, int r)
    {
        ls = rs = nullptr, lps = 0;
        if (l == r)
            return;
        else
            this->ls = new Node(l, l + r >> 1), this->rs = new Node((l + r >> 1) + 1, r);
    }
    void Modify(int l, int r, int pos, int k)
    {
        if (l == r)
            this->lps = k;
        else
        {
            if (pos <= (l + r >> 1))
            {
                this->ls = new Node(this->ls);
                this->ls->Modify(l, l + r >> 1, pos, k);
            }
            else
            {
                this->rs = new Node(this->rs);
                this->rs->Modify((l + r >> 1) + 1, r, pos, k);
            }
            this->pushup();
        }
    }
    int Query(int l, int r, int k)
    {
        if (l == r)
            return l;
        if (this->ls->lps < k)
            return this->ls->Query(l, (l + r >> 1), k);
        else
            return this->rs->Query((l + r >> 1) + 1, r, k);
    }
} *rt[N];
int main()
{
    int n = read(), m = read();
    rt[0] = new Node(0, n);
    for (int i = 1; i <= n; i++)
    {
        int a = read();
        rt[i] = new Node(rt[i - 1]);
        if (a > n)
            continue;
        rt[i]->Modify(0, n, a, i);
    }
    for (int i = 1; i <= m; i++)
    {
        int l = read(), r = read();
        printf("%d\n", rt[r]->Query(0, n, l));
    }
}