题目描述

s7win99 是一名宝石商人。

现在，她有 $n$ 块宝石，第 $i$ 块宝石的价值为 $w_i$。s7win99 想用这 $n$ 块宝石提炼出 恰好一块 最漂亮的宝石。宝石价值越高越漂亮。

每次，s7win99 可以消耗两块宝石 $x, y$，融合出新的宝石 $z$。新宝石 $z$ 的价值 $w_z = \frac{w_x+w_y}{2}$。

s7win99 希望消耗全部的 $n$ 块宝石。因此，s7win99 会重复上述的操作 恰好 $n − 1$ 次。

s7win99 想知道，她可以获得的最漂亮的宝石的价值 最多 是多少。

提示：请 注意并仔细考虑 浮点数在运算时可能产生的精度问题。

输入格式

从文件 jewel.in 中读入数据。

第一行为一个整数 $n$。

第二行为 $n$ 个整数 $w_1, w_2, \dots, w_n$。

输出格式

输出到文件 jewel.out 中。

输出一行一个浮点数，表示最漂亮宝石的价值。

设你输出的答案为 $X$，标准答案为 $Y$ ，若 $\frac{\vert X - Y \vert }{Y} \leq 10^{-5}$，则判定你的答案正确。

5
2 3 4 5 1

4.0625

样例 $1$ 解释

输出 $4.0625001、4.0624999$ 等，由于其满足相对误差不超过 $10^{−5}$，答案亦正确。

见下方附加文件压缩包内 jewel/jewel2.in

见下方附加文件压缩包内 jewel/jewel2.out

样例 $2$ 解释

样例 $2$ 满足 测试点 $11 \sim 12$ 的限制。

见下方附加文件压缩包内 jewel/jewel3.in

见下方附加文件压缩包内 jewel/jewel3.out

数据范围

对于 $100 \%$ 的测试数据，保证 $1 \leq n \leq 10^5, 1 \leq a_i \leq 10^6$。

测试点编号	$n \leq$	特殊性质
$1 \sim 10$	$12$	无
$6 \sim 10$	$500$
$11 \sim 12$	$10^5$	$a_i$ 均相等
$13 \sim 20$		无

附加文件

jewel