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

Those cling-on troubles that ride my stride — cough up the fee, or step aside.
— SHUN, TAKE IT AWAY

Для перестановки$$$^{\text{∗}}$$$ $$$r$$$ длины $$$m$$$ назовём индекс $$$i$$$ ($$$1\le i\le m$$$) уродливым, если и только если $$$i=\max(\{r_1,r_2,\ldots,r_i\})$$$.

У Симона есть перестановка $$$p$$$ длины $$$n$$$, и он может выполнить следующую операцию над $$$p$$$ не более одного раза:

  • Выбрать два индекса $$$i$$$ и $$$j$$$ ($$$1\le i\ne j\le n$$$), затем поменять местами $$$p_i$$$ и $$$p_j$$$.

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

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

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

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

Первая строка содержит целое число $$$n$$$ ($$$1\le n\le 500$$$) — длина $$$p$$$.

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

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$q_1,q_2,\ldots,q_n$$$ — перестановку, которую вы нашли.

Если существует несколько возможных перестановок, вы можете вывести любую.

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

В первом наборе входных данных Симон может получить только две возможные перестановки: $$$[1,2]$$$ и $$$[2,1]$$$.

  • Для перестановки $$$[1,2]$$$ мы видим, что $$$1=\max(\{1\})$$$ и $$$2=\max(\{1,2\})$$$. Таким образом, есть два уродливых индекса.
  • Для перестановки $$$[2,1]$$$ мы видим, что $$$1\ne\max(\{2\})$$$ и $$$2=\max(\{2,1\})$$$. Таким образом, есть только один уродливый индекс.

Перестановка $$$[2,1]$$$ имеет минимальное количество уродливых индексов.

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

  • $$$1\ne \max(\{2\})$$$, так что индекс $$$1$$$ не уродливый;
  • $$$2\ne \max(\{2,4\})$$$, так что индекс $$$2$$$ не уродливый;
  • $$$3\ne \max(\{2,4,1\})$$$, так что индекс $$$3$$$ не уродливый;
  • $$$4=\max(\{2,4,1,3\})$$$, так что индекс $$$4$$$ уродливый.

В третьем наборе входных данных обратите внимание, что Симон не выполняет операцию.