奥斯卡第一个魔术背后的秘密已经揭晓!因为他仍然想给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$$$ 并且不使用任何操作。