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

Одним субботним вечером Егор играл в свою любимую RPG игрушку. Исследуя новые края и земли, он наткнулся на такой знак:

Егор — увлечённый игрок, но ещё и алгоритмист. Поэтому он моментально заметил 4 повторяющиеся буквы на знаке. Более того, если мы переставим буквы «R», «E», «G», «O» из первого слова, то мы получим буквы «O», «G», «R», «E» во втором слове. Егор вдохновился знаком и тотчас придумал задачу о перестановках.

Вам дана перестановка размера $$$n$$$. Вам нужно разбить её на несколько непустых подпоследовательностей так, чтобы каждый элемент перестановки принадлежал ровно одной из подпоследовательностей. Каждая подпоследовательность должна быть монотонной — то есть или возрастающей, или убывающей.

Последовательность называется подпоследовательностью перестановки, если её можно получить из неё удалением нескольких (возможно, ни одного) элементов, не меняя порядок всех остальных элементов.

Количество подпоследовательностей в разбиении должно быть не очень большим. Пусть $$$f(n)$$$ — это минимальное целое число $$$k$$$ такое, что любую перестановку длины $$$n$$$ можно разбить на не более, чем $$$k$$$ монотонных подпоследовательностей.

Вам нужно разбить перестановку на не более, чем $$$f(n)$$$ монотонных подпоследовательностей.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество тестов.

Во взломах вы можете использовать только $$$t = 1$$$.

Далее следуют описания $$$t$$$ тестов.

Первая строка каждого теста содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — длину перестановки. Вторая строка содержит $$$n$$$ целых различных чисел $$$a_i$$$ ($$$1 \leq a_i \leq n$$$) задающих перестановку.

Сумма значений $$$n$$$ по всем тестам не превосходит $$$10^5$$$.

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

Для каждого теста выведите ответ в следующем формате:

В первой строке выведите одно целое число $$$k$$$ ($$$1 \leq k \leq f(n)$$$) — количество последовательностей в разбиении. В следующих $$$k$$$ строках выведите описания найденных подпоследовательностей. Каждое описание начинается с целого числа $$$l_i$$$ ($$$1 \leq l_i \leq n$$$) — длины соответствующей подпоследовательности. Затем следуют $$$l_i$$$ целых чисел — значения чисел в этой подпоследовательности в том порядке, в котором они встречаются в перестановке.

Каждая выведенная вами подпоследовательность должна или возрастать, или убывать.

Пример
Входные данные
3
4
4 3 1 2
6
4 5 6 1 3 2
10
1 2 3 4 5 6 7 8 9 10
Выходные данные
2
3 4 3 1
1 2
3
2 4 1
2 5 6
2 3 2
1
10 1 2 3 4 5 6 7 8 9 10
Примечание

В примере мы можем разбить следующим образом:

  • $$$[4, 3, 1, 2]$$$ на $$$[4, 3, 1]$$$, $$$[2]$$$
  • $$$[4, 5, 6, 1, 3, 2]$$$ на $$$[4, 1]$$$, $$$[5, 6]$$$ и $$$[3, 2]$$$
  • $$$[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$$$ на $$$[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$$$

Разумеется, есть много других возможных вариантов разбиения.