CF2039H1 Cool Swap Walk (Easy Version)

# Cool Swap Walk (Easy Version) 给你一个大小为 $ n $ 的数组 $ a $ 。 下面是一个很酷的交换行走过程： - 你需要从 $(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 ### 样例输入 #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] $ 最初是递减的。 在第一次行走中 - 然后，$ a=[1,2,3] $ 注意，虽然数组 $ a $ 已经是非递减的，但在到达 $ (n,n) $ 之前不能停止。 - 在第 $ 2 $ 步中，你向右走到 $ (1,3) $ . 然后，$ a=[3,2,1] $ . - 在第 $ 3 $ 步中，向下移动到 $ (2,3) $ . 然后，$ a=[3,1,2] $ . - 在第 $ 4 $ 步中，你下到 $ (3,3) $ . 然后，$ a=[3,1,2] $ . 在第二次行走中 - 在第 $ 1 $ 步中，你下到 $ (2,1) $ . 然后，$ a=[1,3,2] $ . - 在第 $ 2 $ 步中，向右走到 $ (2,2) $ . 然后，$ a=[1,3,2] $ . - 在第 $ 4 $ 步中，向下移动到 $ (3,2) $ . 然后，$ a=[1,2,3] $ . - 在第 $ 4 $ 步中，你下到 $ (3,3) $ . 然后，$ a=[1,2,3] $ . 经过上述两次酷交换行走，我们得到 $ a=[1,2,3] $ ，它是不递减的。