这是问题的简单版本。唯一的区别是您可以执行的最大操作数。只有解决了两个版本的问题,你才能进行黑客攻击。
给你一个大小为 $$$n$$$ 的数组 $$$a$$$。
一个很酷的交换行走过程如下:
- 在 $$$n \times n$$$ 网格中,我们将行 $$$i$$$ 和列 $$$j$$$ 中的单元格记为 $$$(i, j)$$$。您需要从 $$$(1,1)$$$ 步行到 $$$(n,n)$$$,仅向右或向下走几步。
- 正式来说,如果您当前位于 $$$(x,y)$$$,则可以步进到 $$$(x+1,y)$$$ 或 $$$(x,y+1)$$$,但不能超出网格边界。
- 当你进入$$$(i,j)$$$时,当$$$i \neq j$$$时,你必须交换$$$a_i$$$和$$$a_j$$$。
你最多可以进行 $$$2n+4$$$ 酷交换行走。按非降序对数组 $$$a_1, a_2, \ldots, a_n$$$ 进行排序。我们可以证明,这样做总是有可能的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 500$$$) — 数组的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots ,a_n$$$ ($$$1 \le a_i \le n$$$) — 数组的元素。
保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$2.5 \cdot 10^5$$$。
输出
对于每个测试用例,您的输出应包含几行:
- 第一行包含一个整数 $$$k$$$ ($$$0 \leq k \leq 2n+4$$$),代表您执行的酷交换行走次数。
- 接下来的 $$$k$$$ 行包含一个长度为 $$$2n-2$$$ 的字符串 $$$s$$$,仅由 R 和 D 组成,表示路径(字母区分大小写)。对于所有 $$$1 \le i \le 2n-2$$$,如果 $$$s_i=$$$ R,则在第 $$$i$$$ 步中向右走,否则在第 $$$i$$$ 步中向下走。
示例
输入 #1
3 2 1 2 3 2 1 3 4 3 2 3 4
输出 #1
0 2 RRDD DRDR 3 RRDRDD DRDDRR DDRRRD
注意
在第一个测试用例中,数组 $$$a$$$ 已经是非递减的,因此您不需要执行任何步行。
在第二个测试用例中,最初 $$$a=[2,1,3]$$$。
第一次行走时:
- 在$$$1$$$-st步骤中,你向右走到$$$(1,2)$$$。那么$$$a=[1,2,3]$$$。请注意,虽然数组 $$$a$$$ 已经是非递减的,但在达到 $$$(n,n)$$$ 之前不能停止。
- 在第 $$$2$$$ 步中,您向右走到 $$$(1,3)$$$。那么$$$a=[3,2,1]$$$。
- 在 $$$3$$$-rd 步骤中,您将下降到 $$$(2,3)$$$。那么$$$a=[3,1,2]$$$。
- 在第 $$$4$$$ 步中,您将下降到 $$$(3,3)$$$。那么$$$a=[3,1,2]$$$。
在第二次行走中:
- 在 $$$1$$$-st 步骤中,您将下降到 $$$(2,1)$$$。那么$$$a=[1,3,2]$$$。
- 在第 $$$2$$$ 步骤中,您向右走到 $$$(2,2)$$$。那么$$$a=[1,3,2]$$$。
- 在 $$$3$$$-rd 步骤中,您将下降到 $$$(3,2)$$$。那么$$$a=[1,2,3]$$$。
- 在第$$$4$$$步骤中,您将下降到$$$(3,3)$$$。那么$$$a=[1,2,3]$$$。
经过上面两次很酷的交换遍历,我们得到 $$$a=[1,2,3]$$$,它是非递减的。