Shared code

#include <stdio.h>

#define N 100000
#define Q 200000

int n, q, h[N], a[Q], b[Q], sta[N], ff[N], ii[Q], ans[Q], top;

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; ++i)
        scanf("%d", &h[i]);

    for (int i = 0; i < q; ++i) {
        scanf("%d%d", &a[i], &b[i]);
        ++ff[--a[i]], --b[i];
    }
    for (int i = n - 2; i >= 0; --i)
        ff[i] += ff[i + 1];
    for (int i = 0; i < q; ++i)
        ii[--ff[a[i]]] = i;

    for (int i_ = 0, i = n - 1; i >= 0; --i) {
        while (top && h[sta[top - 1]] <= h[i])
            --top;
        sta[top++] = i;

        for (; i_ < q && a[ii[i_]] == i; ++i_) {
            int k = top;
            for (int j = 1 << 16; j; j >>= 1)
                if (k - j >= 0 && sta[k - j] <= b[ii[i_]])
                    k -= j;
            ans[ii[i_]] = top - k;
        }
    }
    for (int i = 0; i < q; ++i)
        printf("%d\n", ans[i]);

    return 0;
}