H2. Крутые прогулки с обменом (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между двумя версиями задачи — количество операций, которые вы можете сделать. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Вам дан массив $$$a$$$ длины $$$n$$$.

Крутая прогулка с обменом — это следующий процесс:

  • В сетке $$$n \times n$$$ обозначим ячейку в строке $$$i$$$ и столбце $$$j$$$ как $$$(i, j)$$$. Вам нужно пройти от $$$(1,1)$$$ до $$$(n,n)$$$, делая только шаги вправо или вниз.
  • Формально, если вы находитесь в $$$(x,y)$$$ в данный момент, вы можете сделать шаг в $$$(x+1,y)$$$ или $$$(x,y+1)$$$, но вы не можете выйти за границы сетки.
  • Когда вы делаете шаг в $$$(i,j)$$$, вы должны поменять местами $$$a_i$$$ и $$$a_j$$$, если $$$i \neq j$$$.

Вы можете выполнить не более $$$n+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 n+4$$$), представляющее количество крутых прогулок с обменом, которое вы выполняете.
  • Каждая из следующих $$$k$$$ строк содержит строку $$$s$$$ длины $$$2n-2$$$, состоящую только из R и D, представляющую путь (буквы чувствительны к регистру). Для всех $$$1 \le i \le 2n-2$$$, если $$$s_i=$$$ R, то на $$$i$$$-м шаге вы идёте направо, иначе на $$$i$$$-м шаге вы идёте вниз.
Пример
Входные данные
3
2
1 2
3
2 1 3
4
3 2 3 4
Выходные данные
0
2
RRDD
DRDR
3
RRDRDD
DRDDRR
DDRRRD
Примечание

В первом наборе входных данных массив $$$a$$$ уже является неубывающим, поэтому вам не нужно выполнять никаких прогулок.

Во втором наборе входных данных изначально $$$a=[2,1,3]$$$.

На первой прогулке:

  • На $$$1$$$-м шаге вы делаете шаг вправо в клетку $$$(1,2)$$$. Затем, $$$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]$$$.

  • На $$$3$$$-м шаге вы делаете шаг вниз в $$$(3,2)$$$. Тогда, $$$a=[1,2,3]$$$.

  • На $$$4$$$-м шаге вы опускаетесь в $$$(3,3)$$$. Тогда, $$$a=[1,2,3]$$$.

После двух крутых прогулок с обменом, описанных выше, мы получаем $$$a=[1,2,3]$$$, что является неубывающим массивом.