Background

Josh and $N-1$ other people go to eat burgers.

Problem Description

This burger shop has $M$ types of burgers.

Person $i$ likes burger type $b_i$ the most.

All $N$ people will choose their favorite burger.

Now, these $N$ people line up to pick up burgers. Unfortunately, the first person forgets his favorite burger, so he takes a random burger.

The next $N-2$ people will take burgers according to the following rules:

• If his favorite burger is available, he takes it directly.
• Otherwise, he takes a random one.

You need to find the probability that Josh, who is last in line, gets his favorite burger.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain an integer $b_i$.

Output Format

Output one decimal number, representing the probability that Josh, who is last in line, gets his favorite burger.

3
1 2 3

0.5

7
1 2 3 1 1 2 3

0.57142857

Hint

Explanation for Sample 1

The probability that Josh gets his favorite burger is $\frac{1}{3}+\frac{1}{6}=\frac{1}{2}$.

SPJ Scoring

Let the correct answer be $C$, and your answer be $P$. If $\lvert P-C\rvert <10^{-6}$, then you get full score for this test point; otherwise, you get $0$.

Subtasks

This problem uses bundled tests, and the Subtask scores have been slightly adjusted.

• Subtask 1 ($27$ points): It is guaranteed that $N\le 10^5$, $M\le 10^3$.
• Subtask 2 ($33$ points): It is guaranteed that $M\le 10^3$.
• Subtask 3 ($40$ points): No special restrictions.

Constraints

For $100\%$ of the testdata, it is guaranteed that $3\le N\le 10^6$, $1\le b_i\le M\le 5\times 10^5$.

Notes

This problem is translated from Canadian Computing Competition 2020 Senior T5 Josh's Double Bacon Deluxe.

Translated by ChatGPT 5