混合价值

题目描述

你有一个锅和 $N$ 种食材。每种食材都拥有一个称为「价值」的实数值，第 $i$ 个（$1 \leq i \leq N$）食材的价值为 $v_i$。

把 $2$ 个食材放入锅中，它们会消失并生成 $1$ 个新的食材。这个新食材的价值为原来的 $2$ 个食材的价值之和的 $(x + y) / 2$（其中 $x, y$ 为原来的价值），这个新食材也可以再次放入锅中。

将这个食材合成进行 $N - 1$ 次后，最后剩下 $1$ 个食材。求这最后 $1$ 个食材价值能达到的最大值。

输入格式

输入按以下格式从标准输入给出：

$N$
$v_1$ $v_2$ $\ldots$ $v_N$

输出格式

输出最后剩下的 $1$ 个食材价值能达到的最大值所对应的小数（或整数）。

当输出与评测输出的绝对误差或相对误差不超过 $10^{-5}$ 时，判定为正确。

样例

2
3 4

3.5

一开始有 $2$ 个食材时，只能把两个都放入锅中。由价值 $3, 4$ 的食材合成出的食材价值为 $(3 + 4) / 2 = 3.5$。

另外，输出 3.50001、3.49999 等也会被判定为正确。

3
500 300 200

375

这次一开始有 $3$ 个食材，第一次合成时把哪些食材放入锅中有选择余地。选择项有以下 $3$ 种：

• 放入价值 $500, 300$ 的食材，合成价值 $(500 + 300) / 2 = 400$ 的食材。这种情况下，下一次合成要把这个食材和价值 $200$ 的食材放入锅中，合成价值 $(400 + 200) / 2 = 300$ 的食材。
• 放入价值 $500, 200$ 的食材，合成价值 $(500 + 200) / 2 = 350$ 的食材。这种情况下，下一次合成要把这个食材和价值 $300$ 的食材放入锅中，合成价值 $(350 + 300) / 2 = 325$ 的食材。
• 放入价值 $300, 200$ 的食材，合成价值 $(300 + 200) / 2 = 250$ 的食材。这种情况下，下一次合成要把这个食材和价值 $500$ 的食材放入锅中，合成价值 $(250 + 500) / 2 = 375$ 的食材。

因此，最后剩下的 $1$ 个食材价值能达到的最大值是 $375$。

另外，输出 375.0 等也会被判定为正确。

5
138 138 138 138 138

138

数据范围

• $2 \leq N \leq 50$
• $1 \leq v_i \leq 1000$
• 输入中的所有值均为整数