奇数和偶数显然是独立的，我们只考虑其中一种即可。
如果没有要求字典序最小的话，则显然相对位置不变的方案是最优的
那么我们可以直接得到一种合法方案以及最小代价。
我们用 xi 表示第 i 个数是往左，往右还是不变，
那么按 xi 分段后显然每一段是独立的，否则代价一定大了。
那么我们考虑 xi 相同的一段。
如果他们都是向左的，那么我们可以按照从大到小的顺序，每个数字都尽可能向后面放。
而如果都是向右的，我们按照从小到大的顺序每个数字都尽可能往前面放即可。
可以发现，这样的两种放法都可以最小化字典序，
因此都是对的
代码没写，std写的不是人能看的，所以就且写个思路
原文：https://www.cnblogs.com/wzxbeliever/p/11674197.html