题意简述
对于一个长度为 $m$ 的数组 $b$，你可以进行以下两种操作：
- 选择一个索引 $1 \le i \le m-1$，交换 $bi$ 和 $b{i+1}$ 的值。
- 选择一个索引 $1 \le i \le m-2$，交换 $bi$ 和 $b{i+2}$ 的值。
但是，操作 2 最多只能执行一次。
我们定义 $f(b)$ 为将数组 $b$ 以非递减顺序排序所需的最少操作数（可以使用操作 1 和操作 2），$g(b)$ 为仅使用操作 1 所需的最少操作数。
如果 $f(b) = g(b)$，则称数组 $b$ 是“完美的”（perfect）。换句话说，使用操作 2 的能力并不会减少将数组 $b$ 排序所需的操作数，与仅使用相邻交换相比。
给定一个长度为 $n$ 的排列 $a$，你需要回答 $q$ 个查询。每个查询包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le n$)，代表子数组 $a[l \dots r]$。对于每个查询，判断子数组 $a[l \dots r]$ 是否完美。
思路分析
把 std 的解绑 cin 给去掉会 TLE on test 11。纯狗屎。Horrible problem.
一个数组是完美的，当且仅当其中不存在任何一组 $l \leq i \lt j \lt k \leq r$ 满足 $a_i \gt a_j \gt a_k$。
问题就来到了如何快速查找区间内的三元逆序对。
我们枚举每一个 $j$，如果前面存在一个满足条件的 $i$，后面存在一个满足条件的 $k$，那么我们就找到了一个三元逆序对。
对于一个查询 [l, r]，只要它内部包含任意一个三元逆序对，答案就是 NO。
为了能高效地判断，我们关注那些覆盖范围最小的三元逆序对。因为如果一个查询连最小的都无法完整覆盖，那它必然也无法覆盖更大的。
也就是对于每一个 $j$，我们要找到离它最近的满足条件的 $i$ 和 $k$。
这个可以单调栈解决。
记 $l_j$ 表示最大的满足 $i \lt j, a_i \gt a_j$ 的 $i$，$r_j$ 表示最小的满足 $j \lt k, a_j \gt a_k$ 的 $k$。
那么对于每一个 $j$，如果 $l_j$ 和 $r_j$ 都存在的话，$[l_j,r_j]$ 即为一个最小的合法的三元逆序对。
记 $f_{r_q}$ 表示以 $r_q$ 结尾的最近的合法三元逆序对的起始点 $l_q$。前缀最大值一下可以预处理出来。
那么对于每一次查询 $[l_i,r_i]$，我们只需要查询 $r_i$ 对应的最近逆序对起点，如果这个起点在查询区间内，就说明这个区间内存在三元逆序对。