4270. [THUPC 2025 pre] 排序大师2

【题目描述】

由于你是排序大师，你经常被路过的游客刁难，要求用一些奇怪的操作给序列排序。

由于你是远近闻名的排序大师，邻国的排序萌新小 I 慕名前来拜访，留下了一个长度为 $n$ 的排列 $a_1, a_2 \cdots, a_n$，并要求你用以下操作将排列升序排序：

• 选择 $i,j$，满足 $1 \le i, j \le n$ 且 $|j - i| > 1$，交换 $a_i$ 和 $a_j$。

由于你是因精益求精而远近闻名的排序大师，你需要给出一个排序方案最小化操作次数，或者报告以上操作无法将序列排序。如有多种操作次数最少的排序方案，输出任意一种即可。

【输入格式】

本题有多组测试数据。第一行一个整数 $T (T \ge 1)$ 表示测试数据组数。

对于每组测试数据，输入的第一行一个整数 $n(1 \le n \le 10^5)$ 表示排列长度，接下来一行 $n$ 个两两不同的整数 $a_1,a_2,\cdots, a_n (1 \le a_i \le n)$ 表示给出的排列。

保证单个测试点中所有测试数据的 $n$ 的和不超过 $10^5$。

【输出格式】

对于每组测试数据，如果使用题目给出的操作无法将序列排序，输出一行一个整数 -1，否则第一行输出一个整数 $s$ 表示最少的操作步数，接下来 $s$ 行每行两个整数 $i,j$，表示一次操作，你需要保证 $1 \le i, j \le n$ 且 $|j - i| > 1$。

可以证明对于所有可能输入，若可以使用题设操作将序列排序，则 $s \le 5n$。

【样例输入】

2
4
2 3 4 1
2
2 1

【样例输出】

5
2 4
1 4
1 3
2 4
1 4
-1

【样例解释】

对于第一组测试数据，排序过程为 $2341 \to 2143 \to 3142 \to 4132 \to 4231 \to 1234$。可以证明不存在步数更少的方案。

【来源】

清华大学学生算法协会 GitLink 仓库