P16983 [NWERC 2017] 淘汰赛 / Knockout Tournament

译自 [Northwestern Europe Regional Contest (NWERC) 2017](http://2017.nwerc.eu) 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}$。

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