CF1012E.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.

给你一个包含 $n$ 个正整数的数组 $a_1, a_2, \dots, a_n$。你可以执行以下操作任意多次：选择若干个互不相同的下标 $i_1, i_2, \dots, i_k$（其中 $1 \le i_j \le n$），并将位置 $i_1$ 上的数移动到位置 $i_2$，位置 $i_2$ 上的数移动到位置 $i_3$，……，位置 $i_k$ 上的数移动到位置 $i_1$。换言之，该操作对元素进行循环移位：$i_1 \to i_2 \to \ldots \to i_k \to i_1$。

例如，若 $n=4$，数组为 $a_1=10, a_2=20, a_3=30, a_4=40$，你选择了三个下标 $i_1=2$、$i_2=1$、$i_3=4$，则操作后数组变为 $a_1=20, a_2=40, a_3=30, a_4=10$。

你的目标是以最少的操作次数将数组变为非递减有序。额外约束是：所有操作中涉及的循环长度之和不得超过给定数值 $s$。若在满足该约束的前提下无法将数组排序，则你的解法应报告此情况。

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$).

输入的第一行包含两个整数 $n$ 和 $s$（$1 \leq n \leq 200\,000$，$0 \leq s \leq 200\,000$）——分别表示数组的元素个数以及环长度之和的上界。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$——数组的元素（$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.

如果无法通过总长度不超过 $s$ 的若干个轮换将数组排序，则输出单个数字“-1”（引号仅用于清晰起见）。

否则，输出单个数字 $q$——即对数组排序所需的最少操作次数。

接下来的 $2 \cdot q$ 行中，按操作实际应用的顺序输出各操作的描述。第 $i$ 个操作的描述以一行开头，该行包含一个整数 $k$（$1 \le k \le n$），表示该轮换的长度（即所选下标的个数）；下一行应包含 $k$ 个互不相同的整数 $i_1, i_2, \dots, i_k$（$1 \le i_j \le n$），表示该轮换所涉及的下标。

这些轮换的长度之和应小于等于 $s$，且在执行完这 $q$ 个操作后，数组必须是已排序的。

若存在多个具有最优 $q$ 值的可行答案，输出任意一个即可。

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.

在第一个例子中，也可以通过两次总长度为 5 的操作来对数组排序：首先执行循环 $1 \to 4 \to 1$（长度为 2），然后执行循环 $2 \to 3 \to 5 \to 2$（长度为 3）。然而，这将是错误答案，因为题目要求使用最少可能的操作次数，而本例中最小操作次数为 1。

在第二个例子中，可以通过两个总长度为 4 的循环对数组排序（$1 \to 2 \to 1$ 和 $3 \to 4 \to 3$）。然而，无法用更短的循环实现相同效果，而题目要求满足 $s=3$。

在第三个例子中，数组已有序，因此无需任何操作。空循环集合的总长度定义为 0。