Вам дана перестановка \(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\) операций. Вам не нужно минимизировать количество операций.
Выходные данные
Выведите свои операции в следующем формате.
Первая строка должна содержать целое число \(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\).
Примечание
В первом примере:
- В начале, \(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]\) — отсортирована.
Во втором примере перестановка уже отсортирована, поэтому вам не нужно выполнять никаких операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 5 4 1 3
|
5
1 4
1 2
2 5
1 4
4 5
|
|
2
|
9
1 2 3 4 5 6 7 8 9
|
0
|
|
3
|
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
|