题目描述

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

由于你是远近闻名的排序大师，邻国的排序萌新小 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 100000)$ 表示排列长度，接下来一行 $n$ 个两两不同的整数 $a_1,a_2,\cdots, a_n (1 \le a_i \le n)$ 表示给出的排列。

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

输出格式

对于每组测试数据，如果使用题目给出的操作无法将序列排序，输出一行一个整数 -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$。可以证明不存在步数更少的方案。

题目使用协议

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

以下『本仓库』皆指 THUPC2025 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2025pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。