Casal do BipBop

#23

Made by: Bruno Monteiro e Rafael Grandsire

1024MB

0.3s

É hora de Bob e Charlie entrarem em um novo hiperfoco de casal: dancinhas de BipBop. Essa rede social especializada em vı́deos curtos está viralizando mais do que nunca. Como consequência, agora os casais medem o quanto se amam em termos do quão bem conseguem dançar juntos. Em teoria, o estilo de dança BipBop é simples e pode ser usado para praticamente qualquer música. Geralmente, consiste em uma sequência de movimentos, um para cada verso, representado por um número inteiro, já que, francamente, seus movimentos são bem genéricos.

Sempre atrasados, os namorados acabaram de chegar a uma festa. A música já está tocando, mas eles ainda querem impressionar e mostrar que conseguem dançar BipBop mesmo sem saber em qual verso a música realmente está. Então, cada um começa a dançar em um verso aleatório e continua seguindo a coreografia até que algum deles atinja o final da coreografia ou até que descoordenem algum movimento (cada um execute um movimento diferente).

Não existe uma música popular que Bob e Charlie não saibam dançar, então, dada uma música representada por uma sequência de movimentos, um para cada verso, calcule o número esperado de versos em que eles estarão dançando em sincronia, se cada um deles inicialmente acha que a música está tocando em um verso aleatório com probabilidade uniforme.

Input

Na primeira linha, leia um inteiro $N$ $(1 ≤ N ≤ 10^5 )$, o número de movimentos da sequência dada. Na segunda linha, leia $N$ inteiros $V_1 , V_2 , . . . , V_N$ $(1 ≤ V_i ≤ N )$, correspondentes ao movimento associado a cada um dos versos na sequência .

Output

Imprima o número esperado de versos (movimentos) que o casal dançará em sincronia, se cada um deles escolher uma posição uniformemente aleatória. Imprima a resposta como uma fração irredutı́vel $P/Q$, em que $gcd(P, Q) = 1$. Pode ser provado que sempre é possı́vel expressar a resposta dessa forma.

Input Example

Output Example

2
1 1

5/4

Explanation 1:
Note que há 4 maneiras equiprováveis da coreografia ocorrer: tanto Bob quando Charlie podem começar no primeiro ou no segundo verso, com probabilidade $\frac{1}{2}$ de cada um começar em cada um dos versos e portanto probabilidade $\frac{1}{4}$ para cada uma das combinações. Caso ambos comecem no primeiro verso, eles dançarão 2 versos em sincronia. Nas outras três possibilidades, dançarão apenas um verso em sincronia. Assim, temos em média, $2×1/4+ 1×1/4+ 1×1/4+ 1×1/4 = 5/4$ versos em sincronia.

4
1 1 1 1

15/8

7
1 2 1 3 1 2 1

48/49