给定一个序列，你每次可以循环移位一个子序列，在涉及到的所有位置的个数和 $\le$ 给定值 $s$ 的情况下，求最小排序次数，并构造。

首先考虑排列的特殊性质。

考虑置换环。不妨设排列是一个错排。令 $c$ 为置换环个数。

循环移位在置换环上的感性理解是，考虑一个序列 $s$，让后一个数的指向变为前一个数的指向。可以发现，当对于一整个环循环移位的时候，会操作 $n$ 个元素，并使用 $c$ 次操作。

能否更少呢？如果你在做题的时候认真地手模了样例 $4$，那么你就可以得到以下构造：假设所有置换环分别为 $c_{1} \dots c_{m}$，先对 $c_{1,0},c_{1,1},\dots c_{2,0} \dots c_{m,0}$ 这样把所有元素操作一次，此时除了 $c_{m,0},c_{m-1,0} \dots c_{1,0}$ 会按照顺序成为一个置换环之外，其它都会成为一个自环，对这个置换环进行操作即可。$n+c$ 个元素，$2$ 次操作。

考虑对这两种操作进行平衡。具体地，令 $p$ 为对前 $p$ 个置换环进行 $2$ 操作，剩下的进行 $1$ 操作，则最终的操作次数为 $(c-p)+2[p \neq 0]$，涉及元素为 $n+p$。取一个符合条件的次数最小的 $p$ 即可。

现在考虑怎么把问题变成一个排列，也即将原序列中的相同元素更具体地定序。

显然，置换环数量越少越好。

我们可以把问题视为对元素的排序，于是仿照排列的置换环，建立图：对于每一个位置 $i$ 而言，设 $c_1$ 为排序后颜色，$c_2$ 为排序前颜色，则连接 $c_1 \rightarrow c_2$。

为了刻画重标号，所以我们考虑对于每条边额外引入一对 $(u,v)$，表达这条边在重标号之后的意义是从 $u$ 指向 $v$。当需要从 $(u,v)$ 找到一个置换环的时候，会从此开始走，走到 $(v,w)(w,x) \dots (,u)$。可以发现，这是子图上的一个欧拉回路，并且对于任何一条欧拉回路的 $(u,v)$ 而言，假设指向 $(c_u,c_v)$，那么只需要要求 $u$ 位置本身的 $(c_1,c_2)$ 对为 $(c_u,c_v)$：这是容易构造的。

于是我们需要把图拆分成尽可能少的欧拉回路。万幸，这张图本身就是欧拉回路：连通且每个点出入度相等（均为原序列中该颜色出现次数），于是做完了。

时间复杂度 $O(n \log n)$。