背景

译自 Northwestern Europe Regional Contest (NWERC) 2017 Problem K。

原题许可协议为 CC BY-SA。

题目描述

Laura 正在组织一场淘汰赛，她的朋友 Dale 也会参加。Laura 希望通过有利地安排比赛，使 Dale 获胜的概率最大。她不知道该怎么做，于是向你求助。自然地，你拒绝配合这种可鄙的行为——但随后你意识到，这其实是一个很有趣的谜题！

当选手人数是 $2$ 的幂时，锦标赛结构可以递归地描述如下：选手被分成两个人数相等的小组，每个小组各自进行一场淘汰赛，之后两个小组的冠军再进行比赛。选手一旦输掉比赛，就会被淘汰。

当选手人数不是 $2$ 的幂时，初始名单中靠后的若干选手会在第一轮自动晋级，使第二轮剩余选手人数变为 $2$ 的幂，如图 1 所示。

:::align{center}

图 1：一棵有 $5$ 名选手的锦标赛树。选手 C、D 和 E 在第一轮自动晋级。 :::

每名选手都有一个表示实力的评分。评分为 $a$ 的选手与评分为 $b$ 的选手比赛时，以 $\frac{a}{a+b}$ 的概率获胜（并且每场比赛的结果与之前比赛独立）。

作为组织者，Laura 可以任意安排选手的初始出场顺序。请问在有利安排下，Dale 赢得整场锦标赛的最大概率是多少？

输入格式

输入包含：

• 一行一个整数 $n$（$2 \leq n \leq 4096$），表示选手总数。
• 接下来 $n$ 行，每行一个整数 $r$（$1 \leq r \leq 10^5$），表示一名选手的评分。给出的第一个评分是 Dale 的评分。

输出格式

输出在有利安排下 Dale 赢得锦标赛的最大概率。你的答案应当满足绝对误差或相对误差不超过 $10^{-6}$。

4
3
1
2
4

0.364285714

5
1
1
3
3
3

0.125

提示

【数据规模与约定】

对于所有数据，满足 $2 \leq n \leq 4096$，$1 \leq r \leq 10^5$。答案允许绝对误差或相对误差不超过 $10^{-6}$。