Вам дана перестановка \(p\) целых чисел от \(1\) до \(n\), где \(n\) чётно.
Вы хотите отсортировать перестановку. Для этого вы можете проделать ноль и более операций следующего вида:
- выбрать два индекса \(i\) и \(j\), такие что \(2 \cdot |i - j| \geq n\), и поменять \(p_i\) и \(p_j\).
Вы хотите отсортировать перестановку за не более чем \(5 \cdot 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}\)) — индексы элементов, которых нужно поменять в соответствующем обмене.
Обратите внимание, что не требуется минимизировать число проделанных операций. Можно показать, что ответ всегда существует.
Примечание
В первом примере, если поменять элементы с индексами \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 1
|
1
1 2
|
|
2
|
4
3 4 1 2
|
4
1 4
1 4
1 3
2 4
|
|
3
|
6
2 5 3 1 4 6
|
3
1 5
2 5
1 4
|