← 返回题目列表

Codeforces · 1984/G

G. 魔术 II

中文机器翻译题面 查看原题

奥斯卡第一个魔术背后的秘密已经揭晓!因为他仍然想给Lura留下深刻的印象,所以他想出了一个新的想法:他仍然想对$$$[1, 2, \ldots, n]$$$的排列$$$p_1, p_2, \ldots, p_n$$$进行排序。

这次,他选择了一个整数$$$k$$$。他想多次使用以下操作以非降序对排列进行排序:

1. 选择一个长度为 $$$k$$$ 的连续子数组并将其从 $$$p$$$ 中删除。
2. 将连续子数组插入到 $$$p$$$ 中的任意位置(可能是最前面或最后面)。

为了尽可能令人印象深刻,Oscar 希望选择 $$$k$$$ 的最大值,以便他可以对排列进行排序。请帮助他找到最大 $$$k$$$ 以及对排列进行排序的操作序列。您不需要最小化操作数,但最多允许使用 $$$5n^2$$$ 操作。

我们有一个证明,对于最大 $$$k$$$ ,您可以在任意数量的操作中对排列进行排序,您也可以在最多 $$$5n^2$$$ 操作中对其进行排序。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$5 \leq n \leq 10^3$$$) — 排列的长度。

每个测试用例的第二行包含 $$$[1, 2, \ldots, n]$$$ 的排列 $$$p_1, p_2, \ldots, p_n$$$。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^3$$$。

输出

对于每个测试用例,首先在新行上输出所选的 $$$k$$$ 值 ($$$1 \leq k \leq n$$$)。

然后,输出单个整数 $$$m$$$ — 使用的操作数 ($$$0 \leq m \leq 5n^2$$$)。

然后,在接下来的 $$$m$$$ 行中,输出由两个整数 $$$i$$$ 和 $$$j$$$ 表示的操作 ($$$1 \leq i, j \leq n - k + 1$$$),表示删除从索引 $$$i$$$ 开始的子数组并将其替换回索引处的 $$$p$$$ 的操作$$$j$$$。

示例

输入 #1

3
5
5 1 2 3 4
5
2 3 5 4 1
6
1 2 3 4 5 6

输出 #1

4
1
2 1
3
2
1 3
2 1
6
0

注意

在第一个测试用例中,将最后四个数字移到前面就足够了。

在第二个测试用例中,可以证明我们不能有 $$$k = 4$$$ 或 $$$k = 5$$$。通过$$$k = 3$$$,我们可以将前三个数字移到最后,然后将中间的三个数字移到前面来对排列进行排序。

在第三个测试用例中,排列已经排序。我们可以有 $$$k = 6$$$ 并且不使用任何操作。