20451번 - Быстрая сортировка 서브태스크스페셜 저지다국어

Новый процессор UL-2018, разработанный в научной лаборатории, предназначен для быстрой обработки массивов. Ключевой особенностью архитектуры нового процессора является операция расслоения отрезка массива.

Рассмотрим массив $[a_1, a_2, \ldots, a_n]$. Операция расслоения характеризуется двумя целыми числами $l$ и $r$ --- номером первого и последнего элемента отрезка массива, к которому она применяется. Обозначим операцию расслоения отрезка массива $[a_l, a_{l+1}, \ldots, a_r]$ как $S(l, r)$. После выполнения операции $S(l, r)$ элементы массива на этом отрезке переупорядочиваются следующим образом. Сначала располагаются элементы отрезка с позиций $a_{l+1}, a_{l+3}, \ldots$, то есть элементы с позиций $i$, для которых значение $i - l$ нечетно, их относительный порядок остаётся неизменным. Затем идут элементы отрезка $a_l, a_{l+2}, \ldots$, то есть элементы с позиций $i$, для которых значение $i-l$ четно, они также сохраняют свой относительный порядок.

Например, рассмотрим массив $[2, 4, 1, 5, 3, 6, 7, 8]$. После выполнения операции расслоения $S(2, 6)$ изменится порядок элементов на отрезке массива $[4, 1, 5, 3, 6]$. Новый порядок элементов на этом отрезке следующий: $[1, 3, 4, 5, 6]$, а весь массив после выполнения этой операции равен $[2, 1, 3, 4, 5, 6, 7, 8]$. 

Для демонстрации возможностей нового процессора решено было использовать операцию расслоения для реализации алгоритма сортировки массива различных чисел. Задан массив, содержащий $n$ элементов, $1 \le n \le 3000$. Элементы массива --- различные целые числа от $1$ до $n$. Необходимо отсортировать заданный массив по возрастанию, используя не более $15\,000$ операций расслоения отрезка массива. 

Например, приведенный выше массив $[2, 4, 1, 5, 3, 6, 7, 8]$ можно отсортировать, используя две операции расслоения. Сначала выполним продемонстрированную выше операцию $S(2, 6)$, после которой массив принимает вид $[2, 1, 3, 4, 5, 6, 7, 8]$, а затем операцию $S(1, 2)$, массив примет вид $[1, 2, 3, 4, 5, 6, 7, 8]$. 

Требуется написать программу, которая по заданному массиву, определит последовательность не более, чем из $15\,000$ операций расслоения, после выполнения которых заданный массив окажется отсортирован по возрастанию. Минимизировать количество выполненных операций расслоения не требуется, достаточно использовать не более $15\,000$ операций.

Первая строка входных данных содержит целое число $n$ --- количество элементов в заданном массиве ($1 \le n \le 3000$).

Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ --- элементы заданного массива ($1 \le a_i \le n$, все $a_i$ различны). 

В первой строке выходных данных необходимо вывести целое число $k$ --- количество выполненных операций расслоения ($0 \le k \le 15\,000$). 

В последующих $k$ строках необходимо вывести описание самих операций, в порядке их выполнения. Каждая операция описывается двумя целыми числами $l$ и $r$ --- номером первого и последнего элемента отрезка массива, к которому необходимо применить очередную операцию расслоения ($1 \le l < r \le n$).

Следует обратить внимание, что минимизировать число $k$ не требуется. Из возможных последовательностей операций расслоения, содержащих не более $15\,000$ операций, после выполнения которых заданный массив будет отсортирован по возрастанию, можно вывести любую. Гарантируется, что хотя бы одна такая последовательность существует.

Второй тест из примера подробно разобран в условии задачи.

Для третьего теста из примера существует решение из одной операции расслоения, но поскольку минимизировать количество операций не требуется, приведенный в примере ответ также является правильным.