Для подготовки к олимпиаде «Когнитивные Технологии» Мадока решила все задачи в мире на сортировки перестановок. Но жюри смогли удивить ее, и дали задачу, которую она нигде до этого не видела, и она не смогла решить ее. Вот она:
Дана перестановка $$$p_1, p_2, \ldots, p_n$$$. С ней можно выполнять следующую операцию:
Нужно отсортировать перестановку не более, чем за $$$4 \cdot n$$$ операций, либо сообщить, что это невозможно.
Данная задача состоит из нескольких наборов входных данных.
В первой строке каждого набора задано единственное число $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — количество наборов входных данных. Затем идет их описание.
В первой строке каждого набора задано число $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — размер перестановки.
Во второй строке задана перестановка $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$).
Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превосходит $$$2 \cdot 10^5$$$
Для набора входных данных выведите:
Каждую операцию выведите на отдельной строке в формате $$$i, j$$$ $$$(1 \leq i, j \leq n, p_i = 1, |i - j| \leq \frac{n}{2}, i \neq j$$$), означающее, что нужно поменять местами $$$p_i$$$ и $$$p_j$$$.
233 2 143 4 2 1
-1 3 4 2 2 3 3 1
В первом тесте должно выполняться, что $$$|i - j| \le 1$$$, а во втором $$$|i - j| \le 2$$$
Так во втором тесте изначально дана перестановка $$$3, 4, 2, 1$$$, после первой операции она стала $$$3, 1, 2, 4$$$, после второй $$$3, 2, 1, 4$$$, а после третьей $$$1, 2, 3, 4$$$.