传送门：https://atcoder.jp/contests/agc065/tasks/agc065_a
为了方便理解，我们把要求的东西乘一个 $-1$，再把答案序列倒过来；也就是说，我们现在要求 $min_{A'}^{A'为A的排列}(\sum_{i=1}^{N-1}((A_{i+1}-A_{i})$ $mod$ $K))$
比较显然的是，如果我们确定了答案序列的第一个数是多少，那么后面最优的取法就是：设当前序列尾部为 $tl$，每次取还没有放进答案序列的数 $nw$ 里，$|nw-tl|$ 最小的一个，也就是（当我们把 $0$~$K-1$ 顺时针排在一个环上后）$tl$ 顺时针往后移的下一个（元素进入序列之后把它的剩余个数 $-1$，无剩余则从环上删除）；
现在问题转化为要求出最优的开头元素。可以手算几个例子看一下，发现：如果开头元素 $hd$ 出现次数不是所有元素中最多的之一，那么当前答案一定不是最优的。举个例子大概就是：
比如说，当 $m=5$ 时，假设答案序列为：
$0、1、2、3、4、0、1、3、1、3、1$；
观察到，一开始 $0$~$4$ 全部出现，一轮后 $4、2$ 用完了，再一轮后 $0$ 也用完了，最后一轮 $3$ 用完了，只剩下最后一个 $1$；此时，序列开头为 $0$，但结尾轮没有 $0$，我们可以把 $0$ 移到结尾轮里它该在的位置（$1$ 之前），这样我们发现答案只会减少而不会增加，因为 $0$ 在开头时和它之后的 $1$ 的距离现在不在答案中了，但 $0$ 被插入的新位置里，它前后的数原先的距离$=$它与二者的距离之和，也就是说，它的插入只是把原来前后两个元素之间的距离劈开了，对答案的总贡献没变。
因此，最优解中，序列开头的数必须在结尾轮中也有出现，也就是说，它的出现次数一定是所有元素中最大的之一。下面我们只需要决策，当有多个出现次数最多的元素时，我们应该怎么做。
最简单的情况是，所有元素的出现次数都最多为 $1$，此时问题相当于：在所有元素组成的环上去掉一个相邻两点之间的区间，使得剩下的链长最小；这时当然是去掉最大的相邻两点之间区间，也就是说，以两点中的一点为链的开头，另一点为结尾，这样开头就是确定的了。
手画两组，观察到这个结论可以拓展，也就是说，在每个元素最大的出现次数不为 $1$ 时，把所有出现次数最多的元素拿出来，排成一个环，应用刚才的做法即可得到开头（其实画一下可以发现，最后一轮只剩出现次数最多的元素了，前面几轮相当于在环上绕了很多圈，而无论在出现最多的元素里选谁开头，之前绕的圈数显然都是一样的）；随后暴力把答案序列求出来，计算答案即可。离散化+用 $set$ 模拟一下每次取元素的过程求答案序列，时间复杂度 $O(n$ $logn)$。