19263번 - Game of Chairs 다국어

문제

You are participating in a strange game. There are $n$ chairs in a row 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.

입력

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.

출력

Output the expected distance as an irreducible fraction.

제한

힌트