P6305 [eJOI 2018] 循环排序

给定一个长为 $n$ 的数列 $\{a_i\}$ ，你可以多次进行如下操作： 选定 $k$ 个不同的下标 $i_1,i_2\cdots,i_k$（其中 $1\leq i_j\leq n$），然后将 $a_{i_1}$ 移动到下标 $i_2$ 处，将 $a_{i_2}$ 移动到下标 $i_3$ 处，……，将 $a_{i_{k-1}}$ 移动到下标 $i_k$ 处，将 $a_{i_k}$ 移动到下标 $i_1$ 处。 换言之，你可以按照如下的顺序轮换元素：$i_1\rightarrow i_2\rightarrow\cdots\rightarrow i_{k}\rightarrow i_1$。 例如：$n=4,\{a_i\}=\{10,20,30,40\},i_1=2,i_2=3,i_3=4$ ，则操作完成后的 $a$ 数列变为 $\{10,40,20,30\}$。 你的任务是用操作次数最少的方法将整个数列排序成不降的。注意，所有操作中选定下标的个数总和不得超过 $s$ 。如果不存在这样的方法（无解），输出 `-1`。

无

无

【样例一解释】 你可以用两次操作 $1\rightarrow 4\rightarrow 1$ 和 $2\rightarrow 3\rightarrow 5\rightarrow 2$ 排序数组，但这样会 WA，因为你的任务是最小化 $q$ ，而最优解的 $q=1$。 一种可行的方法是 $1\rightarrow 4\rightarrow 2\rightarrow 3\rightarrow 5\rightarrow 1$，即样例输出。 【样例二解释】 所有操作中选定下标的个数总和的最小值为 $4$（一种可行的方法是 $1\rightarrow 2\rightarrow 1$ 和 $3\rightarrow 4\rightarrow 3$），因此无解。 【样例三解释】 数组已经有序，因此不需要进行操作。 补充说明：样例 4 和 5 满足子任务 6 和 7 的限制。 --- 【数据范围】 对于 $100\%$ 的数据：$1\leq n\leq 2\times 10^5$，$0\leq s\leq 2\times 10^5$，$1\leq a_i\leq 10^9$。 | 子任务编号 | 分数 | 限制 | | :-----------: | :-----------: | :-----------: | | $1$ | $0$ | 样例 | | $2$ | $5$ | $n,s\leq 2 且 1\leq a_i\leq 2$ | | $3$ | $5$ | $n\leq 5$ | | $4$ | $5$ | $1\leq a_i\leq 2$ | | $5$ | $10$ | $a 是个排列，s=2\times n$ | | $6$ | $10$ | $a 是个排列，n\leq 10^3$ | | $7$ | $15$ | $a 是个排列$ | | $8$ | $15$ | $s=2\times n$ | | $9$ | $15$ | $n\leq 10^3$ | | $10$ | $20$ | 无特殊限制 | --- 来源：[eJOI2018](http://ejoi2018.org/) Problem F「Cycle Sort」 说明：翻译来自 [LOJ](https://loj.ac/problem/2818)