Одним субботним вечером Егор играл в свою любимую RPG игрушку. Исследуя новые края и земли, он наткнулся на такой знак:
Егор — увлечённый игрок, но ещё и алгоритмист. Поэтому он моментально заметил 4 повторяющиеся буквы на знаке. Более того, если мы переставим буквы «R», «E», «G», «O» из первого слова, то мы получим буквы «O», «G», «R», «E» во втором слове. Егор вдохновился знаком и тотчас придумал задачу о перестановках.
Вам дана перестановка размера \(n\). Вам нужно разбить её на несколько непустых подпоследовательностей так, чтобы каждый элемент перестановки принадлежал ровно одной из подпоследовательностей. Каждая подпоследовательность должна быть монотонной — то есть или возрастающей, или убывающей.
Последовательность называется подпоследовательностью перестановки, если её можно получить из неё удалением нескольких (возможно, ни одного) элементов, не меняя порядок всех остальных элементов.
Количество подпоследовательностей в разбиении должно быть не очень большим. Пусть \(f(n)\) — это минимальное целое число \(k\) такое, что любую перестановку длины \(n\) можно разбить на не более, чем \(k\) монотонных подпоследовательностей.
Вам нужно разбить перестановку на не более, чем \(f(n)\) монотонных подпоследовательностей.
Выходные данные
Для каждого теста выведите ответ в следующем формате:
В первой строке выведите одно целое число \(k\) (\(1 \leq k \leq f(n)\)) — количество последовательностей в разбиении. В следующих \(k\) строках выведите описания найденных подпоследовательностей. Каждое описание начинается с целого числа \(l_i\) (\(1 \leq l_i \leq n\)) — длины соответствующей подпоследовательности. Затем следуют \(l_i\) целых чисел — значения чисел в этой подпоследовательности в том порядке, в котором они встречаются в перестановке.
Каждая выведенная вами подпоследовательность должна или возрастать, или убывать.
Примечание
В примере мы можем разбить следующим образом:
- \([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]\)
Разумеется, есть много других возможных вариантов разбиения.