Есть \(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\) лицевой стороной вверх.
Обратите внимание, что вам не нужно минимизировать количество операций.
Выходные данные
В первой строке выведите целое число \(q\) \((0 \leq q \leq n+1)\) — количество операций, которые вы использовали.
В каждой из следующих \(q\) строк выведите по два целых числа \(i\) и \(j\) \((1 \leq i, j \leq n, i \ne j)\) — позиции, которые вы выбрали для очередной операции.
Примечание
Будем обозначать монету \(i\), обращенную лицевой стороной вверх, как \(i\), а монету \(i\), обращенную вниз, как \(-i\).
Последовательность ходов, выполненная в первом примере, изменяет монеты следующим образом:
- \([~~~2,~~~1,~~~3]\)
- \([-3,~~~1,-2]\)
- \([-3,~~~2,-1]\)
- \([~~~1,~~~2,~~~3]\)
Во втором примере монеты изначально находятся на своих местах, поэтому операций не нужно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 1 3
|
3
1 3
3 2
3 1
|
|
2
|
5
1 2 3 4 5
|
0
|