A11904 | Cycle sort

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.