Pinely Round 3 (Div. 1 + Div. 2) |
---|
Закончено |
Вам дана перестановка $$$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$$$.
52 5 4 1 3
5 1 4 1 2 2 5 1 4 4 5
91 2 3 4 5 6 7 8 9
0
106 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
В первом примере:
Во втором примере перестановка уже отсортирована, поэтому вам не нужно выполнять никаких операций.
Название |
---|