题意：给定一个序列 $a$，定义 $f(\{l, r\}) = \{\min(a_{l\dots r}), \max(a_{l\dots r}) \}$，$q$ 次给定 $l, r$，问 $\{l, r\}$ 经过多少次 $f$ 函数后会变为 $\{1, n\}$，或者报告不可能。$n, q\leq 10 ^ 5$，1.5s，1024 MB。
首先看这个多少次，也许可以想到倍增，但是当前的 $(l, r)$ 一共有 $O(n ^ 2)$ 个，无法计算。
后面的表示可能不够严谨，可以认为 $f(l, r)$ 表示上面的函数，会返回一个区间。
下面给出一个结论：
$f(l, r) = f(l, l + 1) \cup f(l + 1, l + 2) \cup \dots \cup f(r - 1, r)$。
证明：设右边的为 $g(l, r)$。首先证明 $g(l, r)\subseteq f(l, r)$。容易发现每一个的 $f(i, i + 1)$ 都是 $\subseteq f(l, r)$ 的，所以 $g(l, r)\subseteq f(l, r)$。然后考虑证明 $f(l, r)\subseteq g(l, r)$。容易发现在最大值和最小值之间的区间，跨度是连续的，也就是每一个 $i\in [l, r]$ 都可以在这段区间中找到一个位置 $p$ 使得 $i\in f(p, p + 1)$，那么 $f(l, r)\subseteq g(l, r)$。综上，$f(l, r) = g(l, r)$。
有了上面的结论，我们就可以发现只需要记录所有的 $f(l, l + 1)$ 即可。
然后考虑倍增，记录所有的 $f ^ {2 ^ i} (l, l + 1)$ 的答案，那么当 $f ^ {2 ^ i}$ 转向 $f ^ {2 ^ {i + 1}}$ 时，我们相当于是求 $f ^ {2 ^ i} (f ^ {2 ^ i}(\{l, l + 1\}))$。里面一层的我们已经知道了，现在要求外面一层的，那么就需要把 $f ^ {2 ^ i}(\{l, r\})$ 区间内部的所有区间都并起来，这个可以使用线段树 / ST 表实现，预处理时间复杂度 $O(n \log ^ 2n)$。
现在开始询问。考虑如何判断 $\{l, r\}$可不可以变成 $\{1, n\}$。容易发现如果超过 $O(n ^ 2)$ 个都还没有出现 $\{1, n\}$ 的话，肯定出现了循环节，但是一出现 $\{1, n\}$ 就一定一直是 $\{1, n\}$ 了（最开始是 $\{1, n\}$ 除外），既然没有出现 $\{1, n\}$，那么就不可能出现 $\{1, n\}$ 了。剩下的直接倍增查找即可，时间复杂度 $O(n \log ^ 2 n + q\log n)$（ST 表，空间复杂度 $O(n\log ^ 2n)$）或者 $O((n + q)\log ^ 2 n)$（线段树，空间复杂度 $O(n\log n)$）。
1 | void prework(int id) |