Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

Есть $$$n$$$ монет, пронумерованных от $$$1$$$ до $$$n$$$. Изначально монета $$$c_i$$$ находится на позиции $$$i$$$ и лежит лицевой стороной вверх (($$$c_1, c_2, \dots, c_n)$$$ является перестановкой чисел от $$$1$$$ до $$$n$$$). Вы можете делать операции с этими монетами.

Одна операция состоит в следующем:

  • Выберите $$$2$$$ различных индекса $$$i$$$ и $$$j$$$.

  • Поменяйте местами монеты на позициях $$$i$$$ и $$$j$$$.

  • Затем переверните обе эти монеты на позициях $$$i$$$ и $$$j$$$ (если они изначально лежали лицевой стороной вверх, то после операции они будут лежать лицевой стороной вниз, и наоборот).

Постройте последовательность из не более чем $$$n+1$$$ операций таким образом, чтобы после выполнения всех операций монета $$$i$$$ находилась на позиции $$$i$$$ лицевой стороной вверх.

Обратите внимание, что вам не нужно минимизировать количество операций.

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

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

Во второй строке содержатся $$$n$$$ целых чисел $$$c_1,c_2,\dots,c_n$$$ ($$$1 \le c_i \le n$$$, $$$c_i \neq c_j$$$ для $$$i\neq j$$$).

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

В первой строке выведите целое число $$$q$$$ $$$(0 \leq q \leq n+1)$$$ — количество операций, которые вы использовали.

В каждой из следующих $$$q$$$ строк выведите по два целых числа $$$i$$$ и $$$j$$$ $$$(1 \leq i, j \leq n, i \ne j)$$$ — позиции, которые вы выбрали для очередной операции.

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

Будем обозначать монету $$$i$$$, обращенную лицевой стороной вверх, как $$$i$$$, а монету $$$i$$$, обращенную вниз, как $$$-i$$$.

Последовательность ходов, выполненная в первом примере, изменяет монеты следующим образом:

  • $$$[~~~2,~~~1,~~~3]$$$
  • $$$[-3,~~~1,-2]$$$
  • $$$[-3,~~~2,-1]$$$
  • $$$[~~~1,~~~2,~~~3]$$$

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