Найдите лексикографически минимальную перестановку

Вам дана перестановка p1,p2,…,pn длины n. Вам нужно выбрать два целых числа l,r (1≤l≤r≤n) и развернуть подотрезок [l,r] перестановки. Перестановка станет равной p1,p2,…,pl−1,pr,pr−1,…,pl,pr+1,pr+2,…,pn .

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

Заметьте, что для двух различных перестановок равной длины 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≤t≤500) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Во второй строке каждого набора входных данных содержатся n целых чисел p1,p2,…,pn (1≤pi≤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].

0