故事背景

傍晚，训练结束的一行人来到夜市里最火的奶茶摊。摊主已经按大家下单的口味一共做了 $N$ 杯奶茶，每个人刚好一杯：谁喜欢什么口味，就做了那种口味的一杯（同一口味可能做了很多杯）。为了不耽误时间，大家按顺序排好队，第一个是粗心的领队，最后一个是你。

可领队把自己点的口味忘得一干二净——他直接在托盘里随机拿起一杯就走。队伍里的其他人依次上前：

• 如果托盘里还有他最喜欢的口味，就拿那一杯；
• 否则，只能在剩下的奶茶中等概率随机拿一杯。

你在队尾默默祈祷：等轮到我时，我还能喝到自己最爱的那一杯吗？

你的任务是算出这种好运发生的概率。

输入格式

• 第一行一个整数 $N$（队伍人数，且也是已经做好的奶茶总数，$3 \le N \le 1\,000\,000$）。

• 第二行包含 $N$ 个整数 $b_1,b_2,\dots,b_N$（$1 \le b_i \le M$，口味编号），表示第 $i$ 个人最喜欢的口味编号。

  • 第 1 个人是领队。
  • 第 $N$ 个人是你。

• 本摊一共提供 $M$ 种口味（$1 \le M \le 500\,000$）。

• 摊主恰好按这份清单做了 $N$ 杯奶茶（也就是口味 $x$ 的杯数等于序列中 $x$ 出现的次数）。

输出格式

输出一个实数 $P$，表示你（第 $N$ 人）最终拿到自己最喜欢口味 $b_N$ 的概率。 若正确答案为 $C$，当 $|P-C|<10^{-6}$ 时判为正确。

样例 1

$输入$

3
1 2 3

$输出$

0.5

$说明$ 领队等概率拿 3 杯中的任意一杯。

• 以 1/3 的概率他拿到自己的口味（1 号），那你就能顺利拿到 3 号；
• 以 1/3 的概率他拿到你的口味（3 号），你必然喝不到；
• 以 1/3 的概率他拿到第 2 人的口味（2 号），此时第 2 人有 1/2 的概率改拿 3 号，从而挡到你。 综合起来，你能喝到 3 号的概率是 $1/3 \times 1 + 1/3 \times 0 + 1/3 \times (1/2) = 1/2$。

样例 2

$输入$

7
1 2 3 1 1 2 3

$输出$

0.57142857

数据范围与部分分