Cycle sort

给定一个长为 $n$ 的数组 $a$。 你可以进行若干次操作。每次操作给出 $k$ 的不同的下标 $i_1, i_2, \ldots, i_k$，然后将这些下标的元素进行顺时针轮换。即：$a_1\to a'_2, a_2\to a'_3, \ldots, a_{k-1}\to a'_k, a_k \to a'_1$。 你希望用这些操作将 $a$ 从小到大排序。现在要求所有操作的 $k$ 的总和不超过 $s$ 的前提下，操作数的最小值。无解输出 `-1`。

You are given an array of $ n $ positive integers $ a_1, a_2, \dots, a_n $ . You can perform the following operation any number of times: select several distinct indices $ i_1, i_2, \dots, i_k $ ( $ 1 \le i_j \le n $ ) and move the number standing at the position $ i_1 $ to the position $ i_2 $ , the number at the position $ i_2 $ to the position $ i_3 $ , ..., the number at the position $ i_k $ to the position $ i_1 $ . In other words, the operation cyclically shifts elements: $ i_1 \to i_2 \to \ldots i_k \to i_1 $ . For example, if you have $ n=4 $ , an array $ a_1=10, a_2=20, a_3=30, a_4=40 $ , and you choose three indices $ i_1=2 $ , $ i_2=1 $ , $ i_3=4 $ , then the resulting array would become $ a_1=20, a_2=40, a_3=30, a_4=10 $ . Your goal is to make the array sorted in non-decreasing order with the minimum number of operations. The additional constraint is that the sum of cycle lengths over all operations should be less than or equal to a number $ s $ . If it's impossible to sort the array while satisfying that constraint, your solution should report that as well.

The first line of the input contains two integers $ n $ and $ s $ ( $ 1 \leq n \leq 200\,000 $ , $ 0 \leq s \leq 200\,000 $ )—the number of elements in the array and the upper bound on the sum of cycle lengths. The next line contains $ n $ integers $ a_1, a_2, \dots, a_n $ —elements of the array ( $ 1 \leq a_i \leq 10^9 $ ).

If it's impossible to sort the array using cycles of total length not exceeding $ s $ , print a single number "-1" (quotes for clarity). Otherwise, print a single number $ q $ — the minimum number of operations required to sort the array. On the next $ 2 \cdot q $ lines print descriptions of operations in the order they are applied to the array. The description of $ i $ -th operation begins with a single line containing one integer $ k $ ( $ 1 \le k \le n $ )—the length of the cycle (that is, the number of selected indices). The next line should contain $ k $ distinct integers $ i_1, i_2, \dots, i_k $ ( $ 1 \le i_j \le n $ )—the indices of the cycle. The sum of lengths of these cycles should be less than or equal to $ s $ , and the array should be sorted after applying these $ q $ operations. If there are several possible answers with the optimal $ q $ , print any of them.

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

In the first example, it's also possible to sort the array with two operations of total length 5: first apply the cycle $ 1 \to 4 \to 1 $ (of length 2), then apply the cycle $ 2 \to 3 \to 5 \to 2 $ (of length 3). However, it would be wrong answer as you're asked to use the minimal possible number of operations, which is 1 in that case. In the second example, it's possible to the sort the array with two cycles of total length 4 ( $ 1 \to 2 \to 1 $ and $ 3 \to 4 \to 3 $ ). However, it's impossible to achieve the same using shorter cycles, which is required by $ s=3 $ . In the third example, the array is already sorted, so no operations are needed. Total length of empty set of cycles is considered to be zero.