C. Crazy Diamond
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$, где $$$n$$$ чётно.

Вы хотите отсортировать перестановку. Для этого вы можете проделать ноль и более операций следующего вида:

  • выбрать два индекса $$$i$$$ и $$$j$$$, такие что $$$2 \cdot |i - j| \geq n$$$, и поменять $$$p_i$$$ и $$$p_j$$$.

Вы хотите отсортировать перестановку за не более чем $$$5 \cdot n$$$ операций. Можно показать, что это всегда можно сделать. Обратите внимание, что не требуется минимизировать число операций.

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

Первая строка содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$n$$$ чётно) — длина перестановки.

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

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

В первой строке выведите $$$m$$$ ($$$0 \le m \le 5 \cdot n$$$) — количество свопов, которое нужно проделать.

В каждой из следующих $$$m$$$ строк выведите два целых числа $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$|a_i - b_i| \ge \frac{n}{2}$$$) — индексы элементов, которых нужно поменять в соответствующем обмене.

Обратите внимание, что не требуется минимизировать число проделанных операций. Можно показать, что ответ всегда существует.

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

В первом примере, если поменять элементы с индексами $$$1$$$ и $$$2$$$ массив станет отсортированным.

Во втором примере обратите внимание на то что не нужно минимизировать число действий.

В третьем примере, после того, как были поменяны местами элементы с индексами $$$1$$$ и $$$5$$$, массив выглядит так: $$$[4, 5, 3, 1, 2, 6]$$$. После того. как были поменяны местами элементы с индексами $$$2$$$ и $$$5$$$, так: $$$[4, 2, 3, 1, 5, 6]$$$. После того, как были поменяны местами элементы с индексами $$$1$$$ и $$$4$$$, массив становится отсортированным: $$$[1, 2, 3, 4, 5, 6]$$$.