题目描述

小 C 在和几个人玩游戏。

一共有 $n$ 人参与，一开始系统会随机安排每个人的位置，让他们排成一列。然后系统会给每个人一个参数 $a_i$。每个回合系统会随机选取一个没有被选取过且没有被淘汰的人，假设这个人是第 $x$ 个人，这个人会淘汰第 $a_x$ 个人。直到所有没有被淘汰的人都被选取后，游戏结束，所有没有被淘汰的人就获胜了。

然而，小 X 是个聪明的人，他想让自己的胜率最大化。

于是，游戏开始前，小 X 悄悄潜入后台，得到了所有 $a_i$ 的值，但这些都无法改变，所以他只能改变系统的选取规则来达到提升胜率的目的。改变后，系统不再随机选取，而是按照小 X 准备的顺序选取，当然，小 X 改变的顺序要使自己胜利的概率最大化。

现在，小 X 想让你求出，修改顺序后小 X 胜利的概率最大是多少。

输入格式

第 $1$ 行一个整数 $n$ 表示有 $n$ 人参与游戏。

第 $2$ 行 $n$ 个正整数表示 $a_i$。

输出格式

一行一个浮点数，表示小 X 最大的胜率。

本题使用 Special Judge，只要与正确答案的误差不超过 $10^{-6}$，即可判断为正确。

5
1 2 5 4 3

0.200000000000

30
1 1 4 5 1 4 1 9 1 9 8 10 1 1 4 5 1 4 1 9 1 9 8 10 1 1 4 5 1 4

0.800000000000

6
2 3 5 3 4 1

0.500000000000

提示

本题采用捆绑测试。

Subtask	$n$	$a_i$	分值
$0$	$1 \le n \le 3 \times 10^3$	无特殊限制	$30$
$1$	无特殊限制	$i \le a_i \le n$	$10$
$2$		$1 \le a_i \le n$ 且 $a_i \ne a_j$	$15$
$3$		无特殊限制	$45$

对于 $100\%$ 的数据，$1 \le n \le 10^5，1 \le a_i \le n$。

样例解释 #1:

小 X 让系统做如下步骤：

• 系统选取第 $4$ 个人，第 $4$ 个人被淘汰了。
• 系统选取第 $1$ 个人，第 $1$ 个人被淘汰了。
• 系统选取第 $3$ 个人，第 $5$ 个人被淘汰了。
• 系统选取第 $2$ 个人，第 $2$ 个人被淘汰了。

最终第 $3$ 个人获胜了，故胜率为 $1 {\div} 5 = 0.2$。

样例解释 #2：

显然，第 $1,4,5,8,9,10$ 个人一定会被淘汰，最终有 $24$ 个人获胜，故胜率为 $24 {\div} 30 = 0.8$。

样例解释 #3:

小 X 让系统做如下步骤：

• 系统选取第 $5$ 个人，第 $4$ 个人被淘汰了。
• 系统选取第 $2$ 个人，第 $3$ 个人被淘汰了。
• 系统选取第 $6$ 个人，第 $1$ 个人被淘汰了。

最终第 $2,5,6$ 个人获胜了，故胜率为 $3 {\div} 6 = 0.5$。