奇点 - 题目

在 2077 年，命题变得非常简单。机器人会通过设定一些随机操作来生成一个问题，然后解决它。命题人只需要检查这个问题是否正确即可。

下面是一个来自 2077 年的问题：

给定一个排列 $p_1, p_2, \dots, p_n$，保证 $n$ 是偶数。你希望仅使用一种操作来对该排列进行排序：

FakeSort(l,r)：你必须保证 $r - l + 1$ 是偶数。设 $k = r - l + 1$，那么连续子序列 $p_l, p_{l+1}, \dots, p_r$ 中最大的 $k/2$ 个元素和最小的 $k/2$ 个元素将分别独立地进行排序。也就是说，设 $L_1, L_2, \dots, L_{k/2}$ 为最大的 $k/2$ 个数的下标，而 $S_1, S_2, \dots, 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, p_{l+1}, \dots, p_r$ 为 $\{5, 7, 1, 8, 6, 4\}$；我们将独立地对该序列中最大的 3 个数和最小的 3 个数进行排序。
$p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$；最大的 3 个数已加粗。排序后，它们变为 $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$。
$p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$；最小的 3 个数已加粗。排序后，它们变为 $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$。

因此，在执行 FakeSort(2,7) 后，$p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ 变为 $\{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, \dots, 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)。

3
4
2 1 4 3
6
3 6 5 1 2 4
8
3 2 1 7 5 4 6 8

QOJ.ac