Новый процессор 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$$$ операций.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \hline 1 & 20 & n \le 100; \ \text{Существует ответ c } k = 1 & \\ \hline 2 & 30 & n \le 100 & 0, 1 \\ \hline 3 & 30 & n \le 1\,000 & 0-2 \\ \hline 4 & 20 & n \le 3\,000 & 0-3 \\ \hline \end{array}$$$$$$

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.