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円$ операций, после выполнения которых заданный массив будет отсортирован по возрастанию, можно вывести любую. Гарантируется, что хотя бы одна такая последовательность существует.

제한

서브태스크

힌트

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

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