Вам дан массив целых положительных чисел \(a_1, a_2, \dots, a_n\). К массиву можно применять следующие операции: выбрать \(k\) различных индексов этого массива \(i_1, i_2, \dots, i_k\) и переместить число, стоящее на позиции \(i_1\) на позицию \(i_2\), число стоящее на позиции \(i_2\) на позицию \(i_3\), ..., число на позиции \(i_k\) на позицию \(i_1\). То есть сдвинуть элементы по циклу \(i_1 \to i_2 \to \ldots i_k \to i_1\).
Вам дано целое неотрицательное число \(s\). Отсортируйте массив с помощью минимально возможного количества таких операций, при условии, что сумма размеров циклов для всех операций не превосходит \(s\), или скажите, что это невозможно.
Первая строка входных данных содержит два целых числа \(n\), \(s\) — количество элементов в массиве и ограничение на сумму размеров циклов (\(1 \leq n \leq 500\,000\), \(0 \leq s \leq 500\,000\)).
В следующей строке находятся \(n\) целых чисел \(a_1, a_2, \dots, a_n\) — элементы массива (\(1 \leq a_i \leq 10^9\)).
Если невозможно с помощью циклов суммарного размера не превосходящего \(s\) отсортировать массив выведите единственное число <<-͡1>>.
В противном случае, сначала выведите единственное число \(q\) — минимально возможное количество операций, с помощью которых можно отсортировать массив.
Далее выведите описание операций в порядке их применения к массиву. Описание каждой операции должно начинаться с одного целого числа \(k\) (\(1 \le k \le n\)) — длины цикла. В следующей строке должны располагаться \(k\) различных целых чисел \(i_1, i_2, \dots, i_k\) (\(1 \le i_j \le n\)) — индексы в цикле.
Сумма длин циклов для всех операций не должна превосходить \(s\), а после применения этих \(q\) операций массив должен быть отсортирован.
Если существует несколько возможных ответов выведите любой.
Задача содержит восемь подзадач.
Для всех тестов данной подзадачи дополнительно выполняются ограничение \(n \leq 5\).
Для всех тестов данной подзадачи дополнительно выполняется условие, что в массиве не более \(2\)-x различных чисел.
Для всех тестов данной подзадачи дополнительно выполняется условие, что любое число от \(1\) до \(n\) встречается в массиве ровно один раз, а также \(s = 2 \cdot n\).
Для всех тестов данной подзадачи дополнительно выполняется условие, что любое число от \(1\) до \(n\) встречается в массиве ровно один раз и выполняется ограничение \(n \leq 1000\).
Для всех тестов данной подзадачи дополнительно выполняется условие, что любое число от \(1\) до \(n\) встречается в массиве ровно один раз.
Для всех тестов данной подзадачи дополнительно выполняется условие \(s = 2 \cdot n\).
Для всех тестов данной подзадачи дополнительно выполняются ограничение \(n \leq 1000\).
Дополнительных ограничений нет.
5 5 3 2 3 1 1
1 5 1 4 2 3 5
4 3 2 1 4 3
-1
2 0 2 2
0
6 9 6 5 4 3 2 1
2 6 1 6 2 5 3 4 3 3 2 1
6 8 6 5 4 3 2 1
3 2 3 4 4 1 6 2 5 2 2 1