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

时间限制:500 ms 内存限制:512 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

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

由于你是远近闻名的排序大师,邻国的排序萌新小 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 查看。