Дана последовательность a1, a2, ..., an, состоящая из различных целых чисел. Требуется разбить эту последовательность на максимальное число подпоследовательностей так, чтобы после сортировки по возрастанию чисел внутри каждой из них итоговая последовательность также оказалась отсортированной по возрастанию.
Под сортировкой по возрастанию чисел внутри подпоследовательности понимается процесс, в котором числа, входящие в подпоследовательность, упорядочиваются по возрастанию, а числа, не входящие в подпоследовательность, не меняют свои позиции.
При разбиении последовательности на подпоследовательности каждый элемент должен войти ровно в одну подпоследовательность.
Выходные данные
В первой строке выведите максимальное число подпоследовательностей k, на которое можно разбить исходную последовательность, выполнив условие задачи.
В следующих k строках выведите описание подпоследовательностей в следующем формате: количество элементов в подпоследовательности ci (0 < ci ≤ n), а затем ci целых чисел l1, l2, ..., lci (1 ≤ lj ≤ n) — индексы этих элементов в исходной последовательности.
Индексы можно выводить в любом порядке. Каждый индекс от 1 до n должен присутствовать в выводе ровно один раз.
Если возможных ответов несколько, выведите любой из них.
Примечание
Пояснение к ответу на первый сэмпл:
После сортировки первой подпоследовательности мы получим последовательность 1 2 3 6 5 4.
После сортировки второй подпоследовательности ничего не изменится.
После сортировки третьей подпоследовательности мы получим последовательность 1 2 3 4 5 6.
После сортировки последней подпоследовательности ничего не изменится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 2 1 6 5 4
|
4
2 1 3
1 2
2 4 6
1 5
|
|
2
|
6
83 -75 -49 11 37 62
|
1
6 1 2 3 4 5 6
|