A. Разворот
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p_1, p_2, \ldots, p_n$$$ длины $$$n$$$. Вам нужно выбрать два целых числа $$$l,r$$$ ($$$1 \le l \le r \le n$$$) и развернуть подотрезок $$$[l,r]$$$ перестановки. Перестановка станет равной $$$p_1,p_2, \dots, p_{l-1},p_r,p_{r-1}, \dots, p_l,p_{r+1},p_{r+2}, \dots ,p_n$$$.

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

Заметьте, что для двух различных перестановок равной длины $$$a$$$ и $$$b$$$, $$$a$$$ лексикографически меньше $$$b$$$, если в первой позиции, где они отличаются, в $$$a$$$ стоит меньший элемент.

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится целое число $$$n$$$ ($$$1 \le n \le 500$$$) — длина перестановки.

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — элементы перестановки.

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

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

Пример
Входные данные
4
1
1
3
2 1 3
4
1 4 2 3
5
1 2 3 4 5
Выходные данные
1 
1 2 3 
1 2 4 3 
1 2 3 4 5
Примечание

В первом наборе входных данных длина перестановки равна $$$1$$$, поэтому единственный возможный отрезок $$$[1,1]$$$. Итоговая перестановка равна $$$[1]$$$.

Во втором наборе входных данных мы можем получить тождественную перестановку с помощью разворота отрезка $$$[1,2]$$$. Итоговая перестановка равна $$$[1,2,3]$$$.

В третьем наборе входных данных наилучшим возможным отрезком является $$$[2,3]$$$. Итоговая перестановка равна $$$[1,2,4,3]$$$.

В четвёртом наборе входных данных не существует меньшей перестановки, поэтому мы можем оставить её, выбрав отрезок $$$[1,1]$$$. Итоговая перестановка равна $$$[1,2,3,4,5]$$$.