猫 Motanel 最喜欢的活动是排序。她面前通常有一排 $N$ 个大小各异的方块，她试图通过一系列交换操作将它们按大小递增的顺序排列。由于猫喜欢成对的东西，所以 $N$ 是偶数。不幸的是，卑鄙的老鼠 Sobo 试图戏弄 Motanel，每当 Motanel 交换第 $i$ 个方块和第 $j$ 个方块时，Sobo 就会接着交换位置 $(N-i+1)$ 和 $(N-j+1)$ 上的方块。Motanel 该如何最优地对这些方块进行排序？

更正式地说，给定一个排列 $P_1, P_2, \dots, P_N$。对索引 $(i, j)$ 的操作定义为：交换 $P_i$ 和 $P_j$，然后交换 $P_{N-i+1}$ 和 $P_{N-j+1}$。

任务

给定 $N$ 和 $P$，创建一个能对 $P$ 进行排序的最小操作序列。

输入格式

每个输入文件中包含多个测试用例。 输入的第一行包含一个整数，表示该文件中的测试用例数量。 每个测试用例的第一行包含一个整数，表示 $N$ 的值。 每个测试用例的下一行包含 $N$ 个整数，分别表示 $P_1, P_2, \dots, P_N$。

输出格式

按顺序输出 $T$ 个测试用例的答案。 如果无法对排列进行排序，只需在新的一行打印 $-1$。 否则，首先输出一行，包含两个整数 $g$ 和 $L$，分别代表你认为的最小操作序列长度，以及你给出的操作序列长度（对于部分分，这两个值可以不同）。然后继续输出 $L$ 行，每行包含两个整数 $i$ 和 $j$。这样的一行表示对索引 $(i, j)$ 的操作。注意，如果你不打算获取重构方案的分数，可以选择令 $L = 0$，更多详情请参阅“评分”部分。如果你打印了负数 $L$ 或进行了无效移动，该测试用例的子任务将得 0 分。无效移动 $(i, j)$ 指的是 $i = j$ 或者其中一个位置超出了范围 $[1, N]$。

数据范围

在所有测试中，$2 \le N \le 200000$，$N$ 为偶数，$P$ 是一个排列：$1$ 到 $N$ 之间的每个值在 $P$ 中恰好出现一次。

评分

每个子任务将独立评分。你获得的得分是该子任务的分值乘以该子任务中所有测试用例的最小比率。测试用例的比率计算如下：

• 如果存在任何子测试用例你未能正确判断是否存在解，则比率为 $0$。
• 如果整个测试过程中你进行了超过 $3 * 10^6$ 次移动，则比率为 $0$。
• 如果你为测试中的所有子测试用例给出了正确的最优移动重构方案，则该测试的比率为 $1.0$（无论你猜测的最优长度是否正确）。
• 如果你计算出了正确的最小移动次数，并为测试中的所有子测试用例给出了正确的解，则该测试的比率为 $0.7$。
• 如果你计算出了正确的最小移动次数，则该测试的比率为 $0.4$。
• 如果你为每个可解的子测试用例给出了正确的移动重构方案，则该测试的比率为 $0.35$。
• 如果你至少有一个子测试用例的重构方案错误，但正确区分了排列是否可排序，则该测试的比率为 $0.15$。

假设这些标准按此顺序考虑，系数由匹配当前测试用例情况的第一个条件决定。

样例

输入 1

4
6
2 6 4 3 1 5
10
4 9 6 3 1 10 8 5 2 7
4
4 1 3 2
10
7 8 9 10 5 6 1 2 3 4

输出 1

3 3
2 4
2 3
1 2
5 5
2 8
2 5
1 4
1 3
1 2
-1
2 2
2 8
1 7