由于你是排序大师,你经常被路过的游客刁难,要求用一些奇怪的操作给序列排序。
由于你是远近闻名的排序大师,邻国的排序萌新小 I 慕名前来拜访,留下了一个长度为 的排列 ,并要求你用以下操作将排列升序排序:
由于你是因精益求精而远近闻名的排序大师,你需要给出一个排序方案最小化操作次数,或者报告以上操作无法将序列排序。如有多种操作次数最少的排序方案,输出任意一种即可。
本题有多组测试数据。第一行一个整数 表示测试数据组数。
对于每组测试数据,输入的第一行一个整数 表示排列长度,接下来一行 个两两不同的整数 表示给出的排列。
保证单个测试点中所有测试数据的 的和不超过 。
对于每组测试数据,如果使用题目给出的操作无法将序列排序,输出一行一个整数 -1,否则第一行输出一个整数 表示最少的操作步数,接下来 行每行两个整数 ,表示一次操作,你需要保证 且 。
-1
可以证明对于所有可能输入,若可以使用题设操作将序列排序,则 。
复制2 4 2 3 4 1 2 2 1
2 4 2 3 4 1 2 2 1
复制5 2 4 1 4 1 3 2 4 1 4 -1
5 2 4 1 4 1 3 2 4 1 4 -1
对于第一组测试数据,排序过程为 。可以证明不存在步数更少的方案。
来自 2025 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2025)初赛。
题解等资源可在 https://gitlink.org.cn/thusaa/thupc2025pre/tree/master 查看。