新一代外部存储器包含整数数组$$$a[1 \ldots n] = [a_1, a_2, \ldots, a_n]$$$。
这种类型的内存不支持更改任意元素的值。相反,它允许您剪切给定数组的任何段,按任何偏移量循环移位(旋转)并将其插入回同一位置。
从技术上讲,每个循环移位由两个连续的操作组成:
1. 您可以选择任意索引 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$) 作为段的边界。
2. 然后将段 $$$a[l \ldots r]$$$ 替换为其向左循环移位任意偏移量 $$$d$$$。循环移位的概念还可以通过以下关系来解释:序列 $$$[1, 4, 1, 3]$$$ 是序列 $$$[3, 1, 4, 1]$$$ 向左循环移位偏移量 $$$1$$$,序列 $$$[4, 1, 3, 1]$$$ 是序列 $$$[3, 1, 4, 1]$$$ 向左偏移$$$2$$$。
例如,如果 $$$a = [1, \color{blue}{3, 2, 8}, 5]$$$,则选择 $$$l = 2$$$、$$$r = 4$$$ 和 $$$d = 2$$$ 将生成一个线段 $$$a[2 \ldots 4] = [3, 2, 8]$$$。然后将该段向左移动偏移量 $$$d = 2$$$,得到一个段 $$$[8, 3, 2]$$$,然后它取代该段的原始元素。最后你得到$$$a = [1, \color{blue}{8, 3, 2}, 5]$$$。
使用不超过 $$$n$$$ 任何段的循环移位对给定数组 $$$a$$$ 进行排序。请注意,您不需要最小化循环移位的数量。任何需要 $$$n$$$ 或更少循环移位的方法都将被接受。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
接下来的 $$$2t$$$ 行包含测试用例的描述。
每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 50$$$) — 数组的长度。第二行由数组 $$$a_i$$$ 中以空格分隔的元素组成 ($$$-10^9 \leq a_i \leq 10^9$$$)。数组 $$$a$$$ 的元素可以重复并且不必是唯一的。
输出
打印所有输入测试用例的 $$$t$$$ 答案。
每个测试用例答案的第一行应包含一个整数 $$$k$$$ ($$$0 \le k \le n$$$) — 对数组进行排序的操作数。接下来的 $$$k$$$ 行应包含格式为“$$$l$$$ $$$r$$$ $$$d$$$”(不带引号)的操作描述,其中 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$) 是要移动的段的边界,而 $$$d$$$ ($$$1 \le d \le r - l$$$)是偏移值。请记住,仅考虑向左循环移位,因此所选段将向左移动偏移量 $$$d$$$。
请注意,您不需要找到排序所需的最小循环移位数。任何轮班次数不超过 $$$n$$$ 的排序方法都将被接受。
如果给定的数组 $$$a$$$ 已经排序,则可能的答案之一是 $$$k = 0$$$ 和一个空的循环移位序列。
如果有多个可能的答案,您可以打印其中任何一个。
示例
输入 #1
4 2 2 1 3 1 2 1 4 2 4 1 3 5 2 5 1 4 3
输出 #1
1 1 2 1 1 1 3 2 3 2 4 1 2 3 1 1 3 2 4 2 4 2 1 5 3 1 2 1 1 3 1
注意
示例中第四个数据集的解释:
1. 段 $$$a[2 \ldots 4]$$$ 被选中,并向左移动 $$$2$$$: $$$[2, \color{blue}{5, 1, 4}, 3] \longrightarrow [2, \color{blue}{4, 5, 1}, 3]$$$
2. 然后选择段 $$$a[1 \ldots 5]$$$ 并向左移动 $$$3$$$: $$$[\color{blue}{2, 4, 5, 1, 3}] \longrightarrow [\color{blue}{1, 3, 2, 4, 5}]$$$
3. 之后,段 $$$a[1 \ldots 2]$$$ 被选中,并向左移动 $$$1$$$: $$$[\color{blue}{1, 3}, 2, 4, 5] \longrightarrow [\color{blue}{3, 1}, 2, 4, 5]$$$
4. 最后,段 $$$a[1 \ldots 3]$$$ 被选中,并向左移动 $$$1$$$: $$$[\color{blue}{3, 1, 2}, 4, 5] \longrightarrow [\color{blue}{1, 2, 3}, 4, 5]$$$