Вам дана перестановка \(p_1, p_2, \dots, p_n\) элементов \([1, 2, \dots, n]\). Вы можете выполнить следующую операцию некоторое количество раз (возможно, \(0\)):
Отсортируйте перестановку не более чем за \(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
7000 ms 1024 Mb Правила оформления программ и список ошибок при автоматической проверке задач