背景

试题来自 清华大学学生算法协会。

题目描述

在 $2077$ 年，出题变得十分简单。机器人会随机设定一些操作来生成一道题目，然后将其解决。出题人只需要检查题目是否正确即可。

下面是一道来自 $2077$ 年的题目：

给定一个排列 $p_1, p_2, \cdots, p_n$，保证 $n$ 是偶数。你希望仅使用一种操作来将这个排列排序：

• FakeSort(l, r)：你必须保证 $r - l + 1$ 是偶数。令 $k = r - l + 1$，则连续子序列 $p_l, p_{l+1}, \cdots, p_r$ 中最大的 $k/2$ 个元素和最小的 $k/2$ 个元素将被各自独立排序。具体而言，设 $L_1, L_2, \cdots, L_{k/2}$ 为最大的 $k/2$ 个数的下标，$S_1, S_2, \cdots, S_{k/2}$ 为最小的 $k/2$ 个数的下标。我们首先将下标 $L_1 \sim L_{k/2}$ 上的数排序，然后将下标 $S_1 \sim S_{k/2}$ 上的数排序。

下面是一个具体例子：假设排列为 $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$。若调用 FakeSort(2,7)：

• $k = r - l + 1 = 6$。连续子序列 $p_l, \cdots, p_r$ 为 $\{5, 7, 1, 8, 6, 4\}$；我们将分别对该序列中最大的 $3$ 个数和最小的 $3$ 个数进行排序。
• $p = \{2, 5, \textbf{7}, 1, \textbf{8}, \textbf{6}, 4, 3\}$；最大的 $3$ 个数以粗体标出。排序后变为 $p = \{2, 5, \textbf{6}, 1, \textbf{7}, \textbf{8}, 4, 3\}$。
• $p = \{2, \textbf{5}, 6, \textbf{1}, 7, 8, \textbf{4}, 3\}$；最小的 $3$ 个数以粗体标出。排序后变为 $p = \{2, \textbf{1}, 6, \textbf{4}, 7, 8, \textbf{5}, 3\}$。

因此 $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ 经过 FakeSort(2,7) 后变为 $\{2, 1, 6, 4, 7, 8, 5, 3\}$。

请使用不超过 $114$ 次操作将排列排序，或判定这不可能。可以证明，如果一个排列能通过该操作排序，则一定存在一种使用不超过 $114$ 次操作的方法。

输入格式

输入包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。

对于每组测试用例，第一行包含一个偶数 $n$ ($4 \le n \le 10^5$)，表示排列的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \cdots, p_n$ ($1 \le p_i \le n$)，即你需要排序的排列。保证 $p$ 是一个排列。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每组测试用例，如果无法将排列排序，输出 -1。

否则，输出一个整数 $k$ ($0 \le k \le 114$)，表示使用的操作次数。

接下来的 $k$ 行，每行输出 $l, r$ ($1 \le l \le r \le n$，$r - l + 1$ 为偶数)，表示执行 FakeSort(l, r)。

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

1
1 4
-1
2
4 7
1 6

提示

翻译由 DeepSeek V4 Pro 完成