B. Сортировка сдвигами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во внешней памяти нового поколения расположен массив целых чисел $$$a[1 \ldots n] = [a_1, a_2, \ldots, a_n]$$$.

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

Формально, один такий циклический сдвиг состоит из двух последовательных действий:

  1. Выбрать произвольные $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$) — границы изменяемого подотрезка массива.
  2. Заменить подотрезок массива $$$a[l \ldots r]$$$ на его циклический сдвиг влево на произвольную величину $$$d$$$. Поясним понятие циклический сдвиг: последовательность $$$[1, 4, 1, 3]$$$ является циклическим сдвигом последовательности $$$[3, 1, 4, 1]$$$ на $$$1$$$ влево. Последовательность $$$[4, 1, 3, 1]$$$ является циклическим сдвигом последовательности $$$[3, 1, 4, 1]$$$ на $$$2$$$ влево.

Например, если $$$a = [1, \color{blue}{3, 2, 8}, 5]$$$, то при выборе $$$l = 2$$$, $$$r = 4$$$ и $$$d = 2$$$ получается подотрезок $$$a[2 \ldots 4] = [3, 2, 8]$$$. Затем этот отрезок сдвигается на $$$d = 2$$$ влево, и получается подотрезок $$$[8, 3, 2]$$$, который в итоге встает на место исходных элементов отрезка. Получается $$$a = [1, \color{blue}{8, 3, 2}, 5]$$$.

Отсортируйте заданный массив $$$a$$$, используя не более $$$n$$$ циклических сдвигов любых его отрезков. Обратите внимание, что вам не нужно минимизировать количество циклических сдвигов. Подойдет любой способ, который требует $$$n$$$ или менее циклических сдвигов.

Входные данные

В первой строке записано целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

В следующих $$$2t$$$ строках даны описания наборов входных данных.

В описании каждого набора входных данных первая строка содержит целое число $$$n$$$ ($$$2 \leq n \leq 50$$$) — длину массива, а во второй строке через пробел перечислены элементы массива $$$a_i$$$ ($$$-10^9 \leq a_i \leq 10^9$$$). Элементы массива $$$a$$$ могут повторяться, то есть не обязаны быть уникальными.

Выходные данные

Выведите $$$t$$$ ответов на все наборы входных данных.

Первая строка ответа на набор входных данных должна содержать число $$$k$$$ ($$$0 \le k \le n$$$) — количество действий, которыми сортируется массив. Следующие $$$k$$$ строк должны содержать описания действий в формате «$$$l$$$ $$$r$$$ $$$d$$$» (без кавычек), где $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$) — это границы сдвигаемого отрезка, а $$$d$$$ ($$$1 \le d \le r - l$$$) — величина сдвига. Напоминаем, что по условию задачи рассматриваются циклические сдвиги влево, и выбранный отрезок будет сдвинут на $$$d$$$ влево.

Обратите внимание, что от вас не требуется найти минимальное необходимое для сортировки количество циклических сдвигов. Подойдет любой способ сортировки, количество сдвигов в котором не превосходит $$$n$$$.

Если заданный массив $$$a$$$ уже отсортирован, то одним из возможных ответов является $$$k = 0$$$ и пустая последовательность циклических сдвигов.

Если возможных ответов несколько, выведите любой из них.

Пример
Входные данные
4
2
2 1
3
1 2 1
4
2 4 1 3
5
2 5 1 4 3
Выходные данные
1
1 2 1
1
1 3 2
3
2 4 1
2 3 1
1 3 2
4
2 4 2
1 5 3
1 2 1
1 3 1
Примечание

Пояснение к четвертому набору данных в примере:

  1. Выбирается отрезок $$$a[2 \ldots 4]$$$ и сдивгается на $$$2$$$ влево: $$$[2, \color{blue}{5, 1, 4}, 3] \longrightarrow [2, \color{blue}{4, 5, 1}, 3]$$$
  2. Выбирается отрезок $$$a[1 \ldots 5]$$$ и сдвигается на $$$3$$$ влево: $$$[\color{blue}{2, 4, 5, 1, 3}] \longrightarrow [\color{blue}{1, 3, 2, 4, 5}]$$$
  3. Выбирается отрезок $$$a[1 \ldots 2]$$$ и сдвигается на $$$1$$$ влево: $$$[\color{blue}{1, 3}, 2, 4, 5] \longrightarrow [\color{blue}{3, 1}, 2, 4, 5]$$$
  4. Выбирается отрезок $$$a[1 \ldots 3]$$$ и сдвигается на $$$1$$$ влево: $$$[\color{blue}{3, 1, 2}, 4, 5] \longrightarrow [\color{blue}{1, 2, 3}, 4, 5]$$$