题解

题意重述：一条直线铁路上有 $N$ 个站点，给定每站“旅客流量” $L_i$。第 $j$ 类列车在且仅在 $L_i\ge j$ 的站停车（双向）。对每个询问 $(A,B)$，人在站 $A$ 上车，允许任意换乘（在列车停车的站才可换乘、上下车），求到站 $B$ 的最少中途停站次数（不计起终点），可以走回头路。

等价图模型：对每个站 $i$，只保留与之最“关键”的相邻可达关系即可覆盖最短停站数。

• 用单调栈分别求每个站 $i$ 的“左侧第一个不小于 $L_i$ 的站”和“右侧第一个不小于 $L_i$ 的站”，各连一条无向边。这些边张成一张外平面图的骨架图，能在“跨边次数”意义下等价表达最少停站数。
• 直观理解：把折线 $i\mapsto L_i$ 看作山脊，最近更大值边把相邻“山峰/山谷”连接起来；在此骨架上从 $A$ 到 $B$ 的最少跨边次数即为答案。

把直线划分为若干块：

• 在相邻站间 $[i,i+1]$，若没有任何“最近更大值”边跨过这条缝隙，则此处断开，整线被划成若干块。块与块之间通过“桥”相连。
• 任意询问 $(A,B)$：
  • 若 $\mathrm{bel}[A] \ne \mathrm{bel}[B]$，答案先加上跨过的块数减 $1$（即 $\mathrm{bel}[B]-\mathrm{bel}[A]-1$），再分别加上两端在各自块内到边界的最少跨边次数。
  • 若 $\mathrm{bel}[A] = \mathrm{bel}[B]$，仅需在该块内求最少跨边次数。

同块内求解（环 + 弦分治）：

• 若一块内部“边数 $=$ 点数”，其骨架是一条简单环。把块内顶点按在线上的顺序编号，环上两点的最少跨边次数就是两条方向上的环距的较小者。
• 否则，存在一条“弦边”把环切成两段。选择能最小化环上最短弧长的弦 $(u,v)$，分别从 $u$ 与 $v$ 做 BFS，得到 $\mathrm{dis}_u(\cdot),\mathrm{dis}_v(\cdot)$。对于同块内任意询问 $(x,y)$，$$\mathrm{ans}(x,y) \le \min\big(\mathrm{dis}_u(x)+\mathrm{dis}_u(y),\, \mathrm{dis}_v(x)+\mathrm{dis}_v(y)\big). $$然后以该弦将块分成左右两块，仅把端点同属一侧的询问递归下发处理。每条边/点仅被少数递归层访问，均摊近线性。

复杂度与实现要点：

• 单调栈两次扫描建边与断点统计均为 $O(N)$；跨块贡献可按 $\mathrm{bel}[\cdot]$ 直接计算。
• 块内用“简单环直接算 + 弦边两次 BFS + 递归划分”求解，整体时间近似 $O(N+Q)$（常数与实现有关），空间 $O(N)$。

#include <bits/stdc++.h>
#define fs first
#define sc second
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
#define lc ls, l, mid
#define rc rs, mid + 1, r
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define gc getchar
#define pc putchar

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;

const int maxn = 1e6 + 10;
const bool multidata = 0;

template<typename T = int>
T read() {
	T x = 0, f = 1; char c = gc();
	while (c < '0' || c > '9') { if (c == '-') f = -f; c = gc(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc();
	return x * f;
}

template<typename T = int>
void write(T x) {
	if (x < 0) pc('-'), x = -x;
	if (x < 10) return void (pc(x + '0'));
	write<T>(x / 10), pc(x % 10 + '0');
}

struct qry {
	int x, y, id;
};

namespace Main {
	int res[maxn];
	int bl[maxn], br[maxn], bk[maxn];
	int disl[maxn], disr[maxn], vis[maxn];
	vector<int> ng[maxn]; 
	
	void solve(vector<int> V, vector<pii> E, vector<qry> Q) {
		if (V.size() == E.size()) {
			rep(i, 0, V.size() - 1) bk[V[i]] = i + 1;
			for (qry i : Q) res[i.id] = min(res[i.id], (int) min((bk[i.x] - bk[i.y] + V.size()) % V.size(), (bk[i.y] - bk[i.x] + V.size()) % V.size()));
			rep(i, 0, V.size() - 1) bk[V[i]] = 0;
			return;
		}
		for (pii e : E) ng[e.fs].push_back(e.sc), ng[e.sc].push_back(e.fs);
		rep(i, 0, V.size() - 1) bk[V[i]] = i + 1, disl[V[i]] = disr[V[i]] = 1e9;
		pii e; int cur = 1e9;
		for (int u : V) {
			for (int v : ng[u]) {
				int x = max((bk[u] - bk[v] + V.size()) % V.size(), (bk[v] - bk[u] + V.size()) % V.size());
				if (x < cur) cur = x, e = {u, v};
			}
		}
		rep(i, 0, V.size() - 1) vis[V[i]] = 0;
		queue<int> q;
		q.push(e.fs), disl[e.fs] = 0, vis[e.fs] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int v : ng[u]) {
				if (disl[u] + 1 < disl[v]) {
					disl[v] = disl[u] + 1;
					if (!vis[v]) q.push(v), vis[v] = 1;
				}
			}
		}
		rep(i, 0, V.size() - 1) vis[V[i]] = 0;
		q.push(e.sc), disr[e.sc] = 0, vis[e.sc] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int v : ng[u]) {
				if (disr[u] + 1 < disr[v]) {
					disr[v] = disr[u] + 1;
					if (!vis[v]) q.push(v), vis[v] = 1;
				}
			}
		}
		for (qry i : Q) res[i.id] = min(res[i.id], min(disl[i.x] + disl[i.y], disr[i.x] + disr[i.y]));
		rep(i, 0, V.size() - 1) disl[V[i]] = disr[V[i]] = 0, vis[V[i]] = 0;
		int l = bk[e.fs] - 1, r = bk[e.sc] - 1;
		if (l > r) swap(l, r);
		vector<int> Vl, Vr;
		vector<pii> El, Er;
		vector<qry> Ql, Qr;
		rep(i, l, r) Vl.push_back(V[i]), bl[V[i]] = 1;
		rep(i, r, V.size() - 1) Vr.push_back(V[i]), br[V[i]] = 1;
		rep(i, 0, l) Vr.push_back(V[i]), br[V[i]] = 1;
		for (pii e : E) {
			if (bl[e.fs] && bl[e.sc]) El.push_back(e);
			if (br[e.fs] && br[e.sc]) Er.push_back(e);
		}
		for (qry i : Q) {
			if (bl[i.x] && bl[i.y]) Ql.push_back(i);
			if (br[i.x] && br[i.y]) Qr.push_back(i);
		}
		rep(i, 0, V.size() - 1) bl[V[i]] = br[V[i]] = bk[V[i]] = 0, ng[V[i]].clear();
		solve(Vl, El, Ql), solve(Vr, Er, Qr);
	}
}

int n, k, q;
int a[maxn], b[maxn];
int bel[maxn], bl[maxn], br[maxn];
int st[maxn], top;
unordered_map<int, int> bk[maxn];
int res[maxn];
vector<qry> qb[maxn];

void fake_main() {
	n = read(), k = read(), q = read();
	rep(i, 1, n) a[i] = read();
	rep(i, 1, n) {
		while (top && a[st[top]] < a[i]) --top;
		if (top) bk[st[top]][i] = bk[i][st[top]] = 1, ++b[st[top] + 1], --b[i];
		st[++top] = i;
	}
	top = 0;
	per(i, n, 1) {
		while (top && a[st[top]] < a[i]) --top;
		if (top) bk[st[top]][i] = bk[i][st[top]] = 1, ++b[i + 1], --b[st[top]];
		st[++top] = i;
	}
	rep(i, 1, n) b[i] += b[i - 1];
	int cnt = 0;
	rep(i, 1, n) {
		cnt += !b[i], bel[i] = cnt;
		if (!bl[bel[i]]) bl[bel[i]] = i;
		br[bel[i]] = i;
	} 
	rep(i, 1, q) {
		int x = read(), y = read();
		if (x > y) swap(x, y);
		if (x == y) continue;
		if (bel[x] == bel[y]) {
			qb[bel[x]].push_back({x, y, i});
		} else {
			qb[bel[x]].push_back({x, br[bel[x]] + 1, i});
			qb[bel[y]].push_back({bl[bel[y]], y, i});
			res[i] = bel[y] - bel[x] - 1;
		}
	}
	rep(i, 1, bel[n - 1]) {
		for (qry j : qb[i]) Main::res[j.id] = 1e9;
		vector<int> V; vector<pii> E;
		if (bl[i] == br[i]) {
			for (qry j : qb[i]) res[j.id] += (j.x != j.y);
			continue;
		}
		rep(u, bl[i], br[i] + 1) {
			V.push_back(u);
			for (pii k : bk[u]) {
				int v = k.fs;
				if (u < v && v <= br[i] + 1) E.push_back({u, v});
			}
		}
		Main::solve(V, E, qb[i]);
		for (qry j : qb[i]) res[j.id] += Main::res[j.id];
	}
	rep(i, 1, q) write(res[i] - 1), pc('\n'); 
}

signed main() {
	int T = multidata ? read() : 1;
	while (T--) fake_main();
	return 0;
}