AT_relay2_j.Indifferent

有 $2N$ 个陶罐。对于第 $i$ 个陶罐 $($$1 \leq i \leq 2N$$)$，其市场价格为 $p_i$ 日元。

接下来，你和腊肠犬“LunLun”将轮流从中取走一个陶罐。由你先手，直到所有陶罐被你们拿完为止。LunLun 并不知道陶罐的市场价格，因此每次会从剩余的陶罐中等概率随机选一个。而你清楚 LunLun 的行为方式与陶罐的市场价格。

你的目标是通过选择策略，使你拿到的陶罐市场价格总和为 $S$ 日元时，$S$ 的期望最大。请计算在采取最优策略的情况下，$S$ 的最大化期望。

输入从标准输入给出，格式如下：

$N$ $p_1$ $p_2$ ... $p_{2N}$

输出在最优策略下 $S$ 的最大期望。只要输出与标准答案的绝对误差或相对误差不超过 $10^{-9}$，就视为正确。

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq p_i \leq 2 \times 10^5$
• 输入全部为整数。

样例说明 1

显然，应当选择价格为 $15$ 万日元的陶罐。

样例说明 2

你应当先拿走一只 $10$ 万日元的陶罐。剩下的一只 $10$ 万陶罐，有 $2/3$ 的概率在你下一次轮到前不会被 LunLun 拿走。如果被拿走了，只能选择 $5$ 万的陶罐。由此，采取最优策略时 $S$ 的最大期望为 $2/3 \times (100000 + 100000) + 1/3 \times (100000 + 50000) = 183333.3333\ldots$。

由 ChatGPT 5 翻译