Секрет первого фокуса Оскара раскрыт! Поскольку он все еще хочет произвести впечатление на Луру, ему пришла в голову новая идея: он по-прежнему хочет отсортировать перестановку \(p_1, p_2, \ldots, p_n\) из \([1, 2, \ldots, n]\).
На этот раз он выбирает целое число \(k\). Он хочет отсортировать перестановку в неубывающем порядке, используя следующую операцию несколько раз:
- Выбрать непрерывный подмассив длины \(k\) и удалить его из \(p\).
- Вставить непрерывный подмассив обратно в \(p\) на любую позицию (возможно, в самое начало или в самый конец).
Чтобы произвести впечатление, Оскар хочет выбрать максимальное значение \(k\), при котором он сможет отсортировать свою перестановку. Пожалуйста, помогите ему найти максимальное значение \(k\), а также последовательность операций, которые отсортируют перестановку. Вам не нужно минимизировать количество операций, но разрешается использовать не более \(5n^2\) операций.
Можно доказать, что для максимального \(k\), при котором перестановку можно отсортировать за любое количество операций, ее также можно отсортировать за не более чем \(5n^2\) операций.
Выходные данные
Для каждого набора входных данных сначала выведите в отдельной строке выбранное значение \(k\) (\(1 \leq k \leq n\)).
Затем выведите одно целое число \(m\) — количество использованных операций (\(0 \leq m \leq 5n^2\)).
Затем в каждой из следующих \(m\) строк выведите операции, обозначенные двумя целыми числами \(i\) и \(j\) (\(1 \leq i, j \leq n - k + 1\)), представляющие собой операции удаления подмассива, начинающегося с индекса \(i\), и его вставки обратно в \(p\), начиная с индекса \(j\).
Примечание
В первом наборе входных данных достаточно переместить последние четыре числа в начало.
Во втором наборе входных данных можно показать, что мы не можем отсортировать перестановку при \(k = 4\) или \(k = 5\). При \(k = 3\) мы можем переместить первые три числа в конец, а затем средние три —- в начало, чтобы отсортировать перестановку.
В третьем наборе входных данных перестановка уже отсортирована. Мы можем выбрать \(k = 6\) и не использовать никаких операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
5 1 2 3 4
5
2 3 5 4 1
6
1 2 3 4 5 6
|
4
1
2 1
3
2
1 3
2 1
6
0
|