의자 게임

당신은 이상한 게임에 참가한다. 1미터 간격으로 일렬로 놓인 $n$개의 의자가 있다. 각 의자는 $c$가지 색 중 하나로 칠해져 있다.

처음에 당신은 아무 의자에나 앉을 수 있다. 그러면 심사위원이 색 하나를 골라 발표한다. 각 색이 선택될 확률은 $\frac{1}{c}$이다. 당신의 임무는 그 색의 의자로 이동하는 것이다.

물론 가장 가까운 해당 색 의자로 이동한다. 이미 그 의자에 앉아 있다면 전혀 움직이지 않는다.

당신은 처음에 앉을 의자를 잘 골라, 걸어야 하는 거리의 기댓값을 최소화하려 한다.

첫째 줄에 두 정수 $n$과 $c$가 주어진다. $n$은 의자의 수, $c$는 색의 수이다 ($1 \leq c \leq n \leq 10^6$).

둘째 줄에 $n$개의 정수 $a\_i$가 주어진다. $a\_i$는 의자의 색이다 ($1 \leq a\_i \leq c$). 각 색의 의자는 적어도 하나씩 있다.

기댓값을 기약분수로 출력한다.