H. Сортировка параллельными обменами
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
Dubmood - Keygen 8
⠀

Вам дана перестановка $$$p_1, p_2, \dots, p_n$$$ элементов $$$[1, 2, \dots, n]$$$. Вы можете выполнить следующую операцию некоторое количество раз (возможно, $$$0$$$):

  • выбрать подмассив $$$[l, r]$$$ четной длины;
  • поменять местами $$$a_l$$$, $$$a_{l+1}$$$;
  • поменять местами $$$a_{l+2}$$$, $$$a_{l+3}$$$ (если $$$l+3 \leq r$$$);
  • $$$\dots$$$
  • поменять местами $$$a_{r-1}$$$, $$$a_r$$$.

Отсортируйте перестановку не более чем за $$$10^6$$$ операций. Вам не нужно минимизировать количество операций.

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

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

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

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

Выведите свои операции в следующем формате.

Первая строка должна содержать целое число $$$k$$$ ($$$0 \le k \le 10^6$$$) — количество операций.

Следующие $$$k$$$ строк представляют $$$k$$$ операций по порядку. Каждая из этих $$$k$$$ строк должна содержать два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l < r \leq n$$$, $$$r-l+1$$$ должно быть четным) — соответствующая операция заключается в выборе подмассива $$$[l, r]$$$ и перестановке его элементов в соответствии с постановкой задачи.

После всех операций для каждого $$$i$$$ ($$$1 \leq i \leq n$$$) должно выполняться $$$a_i = i$$$.

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

В первом примере:

  • В начале, $$$p = [2, 5, 4, 1, 3]$$$.
  • В первой операции можно выбрать $$$[l, r] = [1, 4]$$$. Тогда $$$(a_1, a_2)$$$ меняются местами и $$$(a_3, a_4)$$$ меняются местами. Новая перестановка — $$$p = [5, 2, 1, 4, 3]$$$.
  • Во второй операции можно выбрать $$$[l, r] = [1, 2]$$$. Тогда $$$(a_1, a_2)$$$ меняются местами. Новая перестановка будет $$$p = [2, 5, 1, 4, 3]$$$.
  • В третьей операции можно выбрать $$$[l, r] = [2, 5]$$$. Тогда $$$(a_2, a_3)$$$ поменяются местами и $$$(a_4, a_5)$$$ поменяются местами. Новая перестановка — $$$p = [2, 1, 5, 3, 4]$$$.
  • В четвертой операции можно выбрать $$$[l, r] = [1, 4]$$$. Тогда $$$(a_1, a_2)$$$ поменяются местами и $$$(a_3, a_4)$$$ поменяются местами. Новая перестановка — $$$p = [1, 2, 3, 5, 4]$$$.
  • В пятой операции можно выбрать $$$[l, r] = [4, 5]$$$. Тогда $$$(a_4, a_5)$$$ поменяются местами. Новая перестановка — $$$p = [1, 2, 3, 4, 5]$$$ — отсортирована.

Во втором примере перестановка уже отсортирована, поэтому вам не нужно выполнять никаких операций.