BipBop 커플

Time limit1sMemory limit1024 MB

Summary

Given N moves, find the expected number of verses two random starts dance in sync before diverging or reaching the end, as a reduced fraction.

Level: Medium7 of 10
Topics: String, String matching, Sorting, Stack
Solved: No attempts yet

문제

Bob and Charlie want to go on the new couple trend, BipBop. This social network for short videos is going viral more than ever. As a result, couples now measure how much they love each other by how well they can dance together. In theory, the BipBop dance style is simple enough to fit almost any song. A song is usually performed as a sequence of moves, one move per verse, where each move is an integer. The moves are fairly generic.

The couple arrives late to a party where the song is already playing. They still want to show they can dance BipBop, even though they do not know which verse the song is on. Each of them starts dancing at a random verse and follows the choreography until one of them reaches the end of the song or they execute different moves.

Given a song as a sequence of moves, one per verse, compute the expected number of verses they dance in sync, assuming each of them picks a starting verse uniformly at random.

입력

The first line contains an integer $N$ ( $1 \le N \le 10^5$ ), the number of verses in the song. The second line contains $N$ integers $V_1, V_2, \dots, V_N$ ( $1 \le V_i \le N$ ), the move for each verse.

출력

Output the expected number of verses the couple dances in sync, as an irreducible fraction $P/Q$ with $\gcd(P, Q) = 1$ . It can be proven that the answer can always be written this way.

Examples3

Example 1
Input
```
2
1 1
```
Expected output
```
5/4
```
Example 2
Input
```
4
1 1 1 1
```
Expected output
```
15/8
```
Example 3
Input
```
7
1 2 1 3 1 2 1
```
Expected output
```
48/49
```