BipBop 커플

밥과 찰리는 새로 유행하는 커플 놀이인 BipBop 트렌드를 즐기려 한다. 짧은 영상에 특화된 이 소셜 네트워크는 그 어느 때보다 빠르게 퍼지고 있다. 그 결과 커플들은 서로를 얼마나 사랑하는지를 함께 춤을 얼마나 잘 맞추는지로 가늠한다. 이론상 BipBop 춤은 단순해서 거의 모든 노래에 쓸 수 있다. 노래는 보통 구절마다 하나씩, 정수로 표현되는 동작의 나열로 이루어진다. 동작들은 꽤 범용적이다.

두 사람은 노래가 이미 재생 중인 파티에 늦게 도착한다. 노래가 지금 어느 구절인지 모르지만, 그래도 BipBop을 출 수 있음을 보여주고 싶어 한다. 각자 임의의 구절에서 춤을 시작해, 둘 중 한 명이 노래의 끝에 도달하거나 서로 다른 동작을 하게 될 때까지 안무를 따라간다.

구절마다 동작이 하나씩 주어진 노래가 있을 때, 두 사람이 각자 시작 구절을 균등한 확률로 고른다고 하자. 두 사람이 동시에 춤을 추는 구절 수의 기댓값을 구하라.

첫 줄에 노래의 구절 수 $N$ ($1 \le N \le 10^5$)이 주어진다. 둘째 줄에는 각 구절의 동작 $V_1, V_2, \dots, V_N$ ($1 \le V_i \le N$)이 $N$개의 정수로 주어진다.

두 사람이 동시에 춤을 추는 구절 수의 기댓값을 기약분수 $P/Q$ ($\gcd(P, Q) = 1$) 꼴로 출력한다. 이 값은 항상 이런 꼴로 쓸 수 있음이 증명되어 있다.