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

Для подготовки к олимпиаде «Когнитивные Технологии» Мадока решила все задачи в мире на сортировки перестановок. Но жюри смогли удивить ее, и дали задачу, которую она нигде до этого не видела, и она не смогла решить ее. Вот она:

Дана перестановка $$$p_1, p_2, \ldots, p_n$$$. С ней можно выполнять следующую операцию:

  • выбрать пару различных индексов $$$i, j$$$ ($$$1 \le i, j \le n$$$), где $$$p_i = 1$$$ и $$$|i - j| \le \frac{n}{2}$$$
  • поменять местами $$$p_i$$$ и $$$p_j$$$.

Нужно отсортировать перестановку не более, чем за $$$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$$$

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

Для набора входных данных выведите:

  • Строку, содержащую единственное число $$$-1$$$, если отсортировать перестановку указанным способом невозможно;
  • Иначе: в первой строке выведите число $$$q$$$ ($$$0 \le q \le 4 \cdot n)$$$ — количество операций. Затем выведите сами операции в порядке выполнения.

    Каждую операцию выведите на отдельной строке в формате $$$i, j$$$ $$$(1 \leq i, j \leq n, p_i = 1, |i - j| \leq \frac{n}{2}, i \neq j$$$), означающее, что нужно поменять местами $$$p_i$$$ и $$$p_j$$$.

Пример
Входные данные
2
3
3 2 1
4
3 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$$$.