将询问离线，按照右端点排序。然后从左往右扫，维护单调递增栈即可。

假设当前扫到 $i$，对于所有右端点在 $i$ 的询问，可以直接在单调栈里二分。

这样做的时间复杂度显然是 $O(n \log n)$。瓶颈在于二分。

#include <cstdio>
#include <algorithm>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )

using namespace std;

void read() { return; }
template <typename T, typename ...T2>
void read(T &s, T2 &...oth) {
    s = 0; char ch = getchar(); bool f = 0;
    for (; ch < '0' or ch > '9'; ch = getchar()) if (ch == '-') f = 1;
    for (; ch >= '0' and ch <= '9'; ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48);
    s = f ? -s : s; read(oth...); return;
}

const int N = 1000010;
int n, m, a[N], stk[N], ans[N], top;
struct Q {
    int l, r, id;
    bool operator < (const Q &t)const {
        return r < t.r;
    }
}q[N];
int solve(int x, int y) {
    int l = 1, r = top;
    while (l < r) {
        int mid = l + r >> 1;
        if (stk[mid] >= x) r = mid;
        else l = mid + 1;
    } return a[stk[l]];
}
int main() {
    read(n, m);
    rep(i, 1, n) read(a[i]);
    rep(i, 1, m) read(q[i].l, q[i].r), q[i].id = i;
    sort(q + 1, q + m + 1); int j = 1;
    rep(i, 1, n) {
        while (j <= m and q[j].r < i) j ++ ;
        while (top and a[stk[top]] <= a[i]) top -- ;
        stk[ ++ top] = i;
        while (j <= m and q[j].r == i)
            ans[q[j].id] = solve(q[j].l, q[j].r), j ++ ;
    }
    rep(i, 1, m) printf("%d\n", ans[i]);
    return 0;
}

然后发现可以将排序改成基数排序，复杂度瓶颈将变为二分栈的复杂度。

但是可以发现，可以利用并查集维护删点，因此时间复杂度变成 $O(n \alpha (n))$。