传送门

中文题目就不在阐述题意

比赛时我们用分块来解决的，但是T掉了。。。

思路：我们使用单调栈维护的每个点可以跳跃到的下一个点，相当于两个点之间可以建一条边（如果不存在下一个点，可以和一个虚拟根结点建边），最后利用倍增求LCA的思想将L，不断向上跳跃，直到不能继续时，当前位置就是最后的位置，两个位置的深度差值就是答案。
///还有一种解法值 单调栈+树状数组+离线

代码：

///#include<bits/stdc++.h>
///#include<unordered_maps>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>

#define MT(a, b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai = acos(-1.0);
const double E = 2.718281828459;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;

template<class T>
inline bool scan_d(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return 0;
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}

int n, op;
int num[100005];
struct node {
    int e;
    int p;
} load[100005];
int head[100005], sign;

inline void add_edge(int s, int e) {
    load[++sign] = node{e, head[s]};
    head[s] = sign;
}

int depth[100005];
int grand[100005][20], N;

void dfs(int s) {
    for (int i = 1; i <= N; i++) {
        grand[s][i] = grand[grand[s][i - 1]][i - 1];
    }
    for (int i = head[s], e; ~i; i = load[i].p) {
        e = load[i].e;
        depth[e] = depth[s] + 1;
        grand[e][0] = s;
        dfs(e);
    }
}

///初始化
inline void init() {
    N = log2(n);
    sign = depth[n + 1] = 0;
    head[n + 1] = -1;
    memset(grand, 0, sizeof(grand));
}

int q[100005]; ///单调栈
int main() {
    int t, s, e;
    scan_d(t);
    while (t--) {
        scan_d(n), scan_d(op);
        init();
        for (int i = 1; i <= n; i++) {
            scan_d(num[i]);
            head[i] = -1;
        }
        for (int i = n, top = 0; i >= 1; i--) {
            while (top != 0 && num[q[top]] <= num[i]) top--;
            if (top == 0) add_edge(n + 1, i);
            else add_edge(q[top], i);
            q[++top] = i;
        }
        dfs(n + 1);
        while (op--) {
            scan_d(s), scan_d(e);
            int l = s;
            for (int i = N; i >= 0; i--) {
                if (grand[s][i] && grand[s][i] <= e && s <= e)
                    s = grand[s][i];
            }
            printf("%d\n", depth[l] - depth[s] + 1);
        }
    }
    return 0;
}