Game of Chairs

Time limit2sMemory limit512 MB

Summary

Choose a starting chair to minimize the expected distance to the nearest chair of a uniformly random color, and output the expectation as a reduced fraction.

Level: Hard8 of 10
Topics: Math, Prefix sum, Brute force, Implementation
Solved: No attempts yet

Problem

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.

Input

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

Output the expected distance as an irreducible fraction.

Examples2

Example 1
Input
```
5 3
1 1 2 3 1
```
Expected output
```
2/3
```
Example 2
Input
```
5 5
1 2 3 4 5
```
Expected output
```
6/5
```