#8949. 「THUPC 2025 初赛」排序大师 2 NOI/NOI+/CTSC

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

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

• 选择 ，满足 且 ，交换 和 。

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

本题有多组测试数据。第一行一个整数 表示测试数据组数。

对于每组测试数据，输入的第一行一个整数 表示排列长度，接下来一行 个两两不同的整数 表示给出的排列。

保证单个测试点中所有测试数据的 的和不超过 。

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

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

样例输入 1

复制2
4
2 3 4 1
2
2 1

样例输出 1

复制5
2 4
1 4
1 3
2 4
1 4
-1

对于第一组测试数据，排序过程为 。可以证明不存在步数更少的方案。

题目来源

来自 2025 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2025）初赛。

题解等资源可在 https://gitlink.org.cn/thusaa/thupc2025pre/tree/master 查看。