P17123 [ICPC 2025 Shanghai R] Singularity

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

在 $2077$ 年，出题变得十分简单。机器人会随机设定一些操作来生成一道题目，然后将其解决。出题人只需要检查题目是否正确即可。 下面是一道来自 $2077$ 年的题目： 给定一个排列 $p_1, p_2, \cdots, p_n$，保证 $n$ 是**偶数**。你希望仅使用一种操作来将这个排列排序： - `FakeSort(l, r)`：你必须保证 $r - l + 1$ 是偶数。令 $k = r - l + 1$，则连续子序列 $p_l, p_{l+1}, \cdots, p_r$ 中最大的 $k/2$ 个元素和最小的 $k/2$ 个元素将被各自独立排序。具体而言，设 $L_1, L_2, \cdots, L_{k/2}$ 为最大的 $k/2$ 个数的下标，$S_1, S_2, \cdots, S_{k/2}$ 为最小的 $k/2$ 个数的下标。我们首先将下标 $L_1 \sim L_{k/2}$ 上的数排序，然后将下标 $S_1 \sim S_{k/2}$ 上的数排序。 下面是一个具体例子：假设排列为 $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$。若调用 `FakeSort(2,7)`： - $k = r - l + 1 = 6$。连续子序列 $p_l, \cdots, p_r$ 为 $\{5, 7, 1, 8, 6, 4\}$；我们将分别对该序列中最大的 $3$ 个数和最小的 $3$ 个数进行排序。 - $p = \{2, 5, \textbf{7}, 1, \textbf{8}, \textbf{6}, 4, 3\}$；最大的 $3$ 个数以粗体标出。排序后变为 $p = \{2, 5, \textbf{6}, 1, \textbf{7}, \textbf{8}, 4, 3\}$。 - $p = \{2, \textbf{5}, 6, \textbf{1}, 7, 8, \textbf{4}, 3\}$；最小的 $3$ 个数以粗体标出。排序后变为 $p = \{2, \textbf{1}, 6, \textbf{4}, 7, 8, \textbf{5}, 3\}$。 因此 $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ 经过 `FakeSort(2,7)` 后变为 $\{2, 1, 6, 4, 7, 8, 5, 3\}$。 请使用不超过 $114$ 次操作将排列排序，或判定这不可能。可以证明，如果一个排列能通过该操作排序，则一定存在一种使用不超过 $114$ 次操作的方法。

输入包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。 对于每组测试用例，第一行包含一个**偶数** $n$ ($4 \le n \le 10^5$)，表示排列的长度。 第二行包含 $n$ 个整数 $p_1, p_2, \cdots, p_n$ ($1 \le p_i \le n$)，即你需要排序的排列。保证 $p$ 是一个排列。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每组测试用例，如果无法将排列排序，输出 `-1`。 否则，输出一个整数 $k$ ($0 \le k \le 114$)，表示使用的操作次数。 接下来的 $k$ 行，每行输出 $l, r$ ($1 \le l \le r \le n$，$r - l + 1$ 为偶数)，表示执行 `FakeSort(l, r)`。

翻译由 DeepSeek V4 Pro 完成