由题意可以发现一个性质：
\[f[(l, r)] = \bigcup_{i = l}^{r - 1} f[(i, i + 1)]
\]
进而可以推广至：
\[f^k[(l, r)] = \bigcup_{i = l}^{r - 1} f^k[(i, i + 1)]
\]
证明显然，即若 \([l_1, r_1] \cap [l_2, r_2]\)，则 \(f([l_1, r_1] \cup [l_2, r_2]) = f((l_1, r_1)) \cup f((l_2, r_2))\)。
然后可以倍增维护。
设 \(g(i, j, k)\) 表示 \(f^{2^k}[(i, i + 2^j)]\)，正常做就好。时间复杂度 \(\mathcal O(n \log^2 n + q \log n)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 10, K = 18;
int n, q, lg[N], a[N];
struct Node {
int l, r;
Node operator+(const Node &rhs) const {return {min(l, rhs.l), max(r, rhs.r)};}
} g[N][K][K];
inline Node f(int l, int r, int k) {
int ln = lg[r - l];
return g[l][ln][k] + g[r - (1 << ln)][ln][k];
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i < n; i++) g[i][0][0] = {min(a[i], a[i + 1]), max(a[i], a[i + 1])};
for (int j = 1; j < K; j++) {
for (int i = 1; i + (1 << j) <= n; i++) {
g[i][j][0] = g[i][j - 1][0] + g[i + (1 << (j - 1))][j - 1][0];
}
}
for (int k = 1; k < K; k++) {
for (int j = 0; j < K; j++) {
for (int i = 1; i + (1 << j) <= n; i++) {
g[i][j][k] = f(g[i][j][k - 1].l, g[i][j][k - 1].r, k - 1);
}
}
}
while (q--) {
int l, r, ans = 1; cin >> l >> r;
if (r - l + 1 == n) {cout << "0\n"; continue;}
if (l == r) {cout << "-1\n"; continue;}
for (int k = K - 1; k >= 0; k--) {
Node to = f(l, r, k);
if (1 < to.l || to.r < n) l = to.l, r = to.r, ans += (1 << k);
}
Node now = f(l, r, 1);
if (now.l == 1 && now.r == n) cout << ans << '\n';
else cout << "-1\n";
}
return 0;
}