好像没有题解给了一些很重要的东西的证明，可能它对于除了我以外的人都真的过于显然。

但是题解满了，我也懒得新写一篇题解然后找管理放进题解区 这人怎么连现成的社区贡献分都不赚，就只写个证明丢在这了。

---

首先求逆，相差小于 $k$ 的数相对位置不变。这是题解都说了的，问题在于为啥求一个满足这个限制的最优排列就做完了呢？换句话说，为啥这个限制是充分的呢？

事实上，考虑两个满足这个限制的排列 $p$ 和 $q$，我们需要证明 $p$ 一定可以变成 $q$。用 $p$ 关于 $q$ 的逆序对来刻画两个排列之间的不同：$i<j$ 的对数，使得 $q$ 中 $p_i$ 在 $p_j$ 后面。

$p\ne q$ 时我们一定能找到一个 $i$，使得 $q$ 中 $p_i$ 在 $p_{i+1}$ 后面。由于 $p$ 和 $q$ 都满足上述限制，那么一定有 $|p_i-p_{i+1}|\ge k$。交换 $p_i$ 和 $p_{i+1}$ 会使得逆序对数减少，所以 $p$ 一定能变成 $q$。

这就是兔队题解里“限于篇幅不证”的证明，好像不是很长吼。

如果令 $q$ 是满足限制的最优排列，根据证明过程我们还可以得到一个结论：对于 $p_i-p_{i+1}\ge k$，直接交换 $p_i$ 和 $p_{i+1}$ 一定是不劣的。这保证了 @linghuchong_ 的排山倒海气贯长虹（下略）做法的正确性。

另外，求逆以后目标实际上并不是字典序最小。至于为什么在这题里直接求最小字典序是对的，兔队的题解里给出了一种证明。但根据上述结论，我们实际上可以直接得到最优解和字典序最小解是等价的。