CF1984G Magic Trick II

奥斯卡的第一个魔术的秘密已经被揭示！因为他仍然想给 Lura 留下深刻印象，他想出了一个新点子：他仍然想要将一个排列 $p_1, p_2, \ldots, p_n$（$[1, 2, \ldots, n]$ 的一个排列）进行排序。 这一次，他选择一个整数 $k$。他希望通过多次使用以下操作，将排列按非递减顺序排序： 1. 选择一个长度为 $k$ 的连续子数组，并将其从 $p$ 中移除。 2. 将这个连续子数组插入到 $p$ 的任意位置（可以是最前面或最后面）。 为了尽可能令人印象深刻，奥斯卡希望选择最大的 $k$，使得他能够将排列排序。请帮助他找到最大的 $k$，以及一系列能够将排列排序的操作。你不需要最小化操作次数，但最多只能使用 $5n^2$ 次操作。 我们有证明，对于能够用任意次数操作排序的最大 $k$，也一定可以在不超过 $5n^2$ 次操作内完成排序。

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$5 \leq n \leq 10^3$），表示排列的长度。 每个测试用例的第二行包含一个排列 $p_1, p_2, \ldots, p_n$，是 $[1, 2, \ldots, n]$ 的一个排列。 所有测试用例中 $n$ 的总和不超过 $2 \times 10^3$。

对于每个测试用例，首先输出所选择的 $k$ 的值（$1 \leq k \leq n$），占一行。 然后输出一个整数 $m$，表示所用操作的次数（$0 \leq m \leq 5n^2$）。 接下来 $m$ 行，每行输出两个整数 $i$ 和 $j$（$1 \leq i, j \leq n - k + 1$），表示一次操作：将从第 $i$ 个位置开始的长度为 $k$ 的子数组移除，并插入到第 $j$ 个位置。

在第一个测试用例中，只需将最后四个数字移到最前面即可。 在第二个测试用例中，可以证明 $k=4$ 或 $k=5$ 都无法完成排序。对于 $k=3$，可以先将前三个数字移到末尾，再将中间三个移到最前面，即可完成排序。 在第三个测试用例中，排列已经有序。可以选择 $k=6$，且无需任何操作。 由 ChatGPT 4.1 翻译