10 人解决，14 人已尝试。
20 份提交通过，共有 153 份提交。
6.4 EMB 奖励。
单点时限: 2.5 sec
内存限制: 256 MB
You are participating in a strange game. There are $n$ chairs around a round table at a distance of one meter from each other. Each chair is painted by one of $c$ different colors.
At the beginning, you can sit on any chair. Then the jury will choose a color and announce it. Each color has $\frac{1}{c}$ probability to be chosen. Your task is to move to any chair of this color.
Of course, you will move to the nearest appropriate chair. If you are already sitting on it, you will not move at all.
You want to pick a chair to sit at the beginning to minimize the expected distance which you will have to walk.
你正在参加一场奇怪的游戏，绕着一个圆桌有 $n$ 把相邻间隔一米的椅子，每把椅子都被涂成了 $c$ 种颜色中的一种。
在游戏开始的时候，你可以坐在任何一张椅子上，之后裁判会选择并宣布一种颜色，每种颜色有 $\frac{1}{c}$ 的概率被选中，你的任务则是马上移动到一张这种颜色的椅子上。
你当然会移动到最近的合适的椅子上，如果你已经坐在那种颜色椅子上，那就动都不用动了。
你想要选择一张开始时坐的椅子来最小化你需要走动的期望距离。
In the first line there are two integers $n$ and $c$: the number of chairs and the number of colors ($1 \leq c \leq n \leq 10^6$).
The second line contains $n$ integers $a_i$: the colors of chairs ($1 \leq a_i \leq c$). There is at least one chair of each color.
第一行包含两个正整数 $n, c$，分别表示椅子的数量和颜色的数量。($1 \leq c \leq n \leq 10^6$)
第二行包含 $n$ 个正整数，$a_i$ 表示第 $i$ 把椅子的颜色。($1 \leq a_i \leq c$)
保证 $c$ 种颜色的椅子都至少有一把。
Output the expected distance as an irreducible fraction.
以最简分数输出期望距离。
5 3 1 1 2 3 1
2/3
5 5 1 2 3 4 5
6/5
你只能围绕着圆桌移动，按环上距离计算。
10 人解决，14 人已尝试。
20 份提交通过，共有 153 份提交。
6.4 EMB 奖励。