Кран
Есть ( n ) ящиков, которые необходимо погрузить на корабль. Каждый ящик пронумерован от 1 до n, и эти номера определяют порядок погрузки. Однако, из-за ошибки, ящики расположены в случайном порядке. Поскольку пространство в доке ограничено, вам нужно отсортировать ящики, меняя их местами.
У вас есть кран, который работает следующим образом: вы выбираете связанный интервал ящиков четной длины. Затем кран меняет местами первую половину интервала со второй половиной, сохраняя порядок внутри каждой половины. Ваша задача — определить последовательность перемещений крана, которая приведет ящики в правильный порядок.
В программном обеспечении крана есть ошибка: счетчик перемещений работает в 9-ичной системе счисления и может отображать не более 6 цифр. Это означает, что кран перестает работать после 9^6 = 531441 перемещений. Ваше решение должно укладываться в этот предел.
Входные данные
Первая строка входных данных содержит количество тестов T. Далее следуют описания тестов:
Каждый тест начинается с целого числа n, где 1 ≤ n ≤ 10000, обозначающего количество ящиков. В следующей строке дана перестановка чисел {1, 2, ..., n}.
Выходные данные
Для каждого теста выведите одну строку, содержащую m — количество обменов, и m строк, описывающих обмены в порядке их выполнения. Каждый обмен описывается двумя числами — индексами первого и последнего элемента в интервале, который нужно обменять. Используйте стандартную десятичную систему счисления.