D. Перевертыш
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p$$$ длины $$$n$$$.

Перестановкой называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$\{2,3,1,5,4\}$$$ является перестановкой, а $$$\{1,2,2\}$$$ не является ($$$2$$$ встречается дважды), и $$$\{1,3,4\}$$$ тоже не является перестановкой ($$$n=3$$$, но в массиве есть $$$4$$$).

К перестановке $$$p$$$ нужно ровно один раз применить следующую операцию:

  • Сначала вы выбираете отрезок $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$, отрезок —непрерывная последовательность чисел $$$\{p_l, p_{l+1}, \ldots, p_{r-1}, p_r\}$$$) и переворачиваете его. Переворот отрезка означает, что меняются местами пары чисел $$$(p_l, p_r)$$$, $$$(p_{l+1}, p_{r-1})$$$, ..., $$$(p_{l + i}, p_{r - i})$$$ (где $$$l + i \le r - i$$$).
  • Затем вы меняете местами префикс и суффикс: $$$[r+1, n]$$$ и $$$[1, l - 1]$$$ (обратите внимание, что эти отрезки могут быть пустыми).

Например, $$$n = 5, p = \{2, \color{blue}{3}, \color{blue}{1}, 5, 4\}$$$ и был выбран отрезок $$$[l = 2, r = 3]$$$, тогда после переворота отрезка $$$p = \{\color{green}{2}, \color{blue}{1}, \color{blue}{3}, \color{green}{5}, \color{green}{4}\}$$$, затем поменяются местами отрезки $$$[4, 5]$$$ и $$$[1, 1]$$$. Тогда $$$p = \{\color{green}{5}, \color{green}{4}, 1, 3, \color{green}{2}\}$$$. Можно показать, что это максимальный возможный ответ для данной перестановки.

Требуется вывести лексикографически максимальную перестановку, которую можно получить после применения ровно одной такой операции.

Перестановка $$$a$$$ лексикографически больше перестановки $$$b$$$, если существует $$$i$$$ ($$$1 \le i \le n$$$) такое, что $$$a_j = b_j$$$ для $$$1 \le j < i$$$ и $$$a_i > b_i$$$.

Входные данные

В первой строке входных данных задано единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

В первой строке набора задано одно целое число $$$n$$$ ($$$1 \le n \le 2000$$$) — размер перестановки.

Во второй строке задано $$$n$$$ целых чисел: $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — сама перестановка $$$p$$$.

Гарантируется, что сумма значений $$$n$$$ по всем тестам не превышает $$$2000$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите лексикографически максимальную перестановку длины $$$n$$$, которую можно получить из $$$p$$$, применив операцию, описанную в условии ровно один раз.

Пример
Входные данные
9
5
2 3 1 5 4
9
4 1 6 7 2 8 5 3 9
4
4 3 2 1
2
2 1
6
3 2 4 1 5 6
7
3 2 1 5 7 6 4
10
10 2 5 6 1 9 3 8 4 7
4
4 2 1 3
1
1
Выходные данные
5 4 1 3 2 
9 4 1 6 7 2 8 5 3 
3 2 1 4 
1 2 
6 5 3 2 4 1 
7 6 4 5 3 2 1 
9 3 8 4 7 1 10 2 5 6 
3 4 2 1 
1
Примечание

Первый пример разобран в условии.

Во втором примере следует выбрать отрезок $$$[l = 9, r = 9]$$$.

В третьем примере следует выбрать отрезок $$$[l = 1, r = 1]$$$.

В четвертом примере следует выбрать отрезок $$$[l = 1, r = 2]$$$.

В пятом примере следует выбрать отрезок $$$[l = 5, r = 6]$$$.

В шестом примере следует выбрать отрезок $$$[l = 4, r = 4]$$$.

В седьмом примере следует выбрать отрезок $$$[l = 5, r = 5]$$$.