AT_scpc2026_div2_e Opening Magical Box

Lulu 发现了一个装有宝藏的魔法箱。箱子上被施加了 $N$ 种不同类型的魔法咒语，每种类型只各有一种，只有以正确的顺序解除所有咒语才能打开箱子。Lulu 作为天才魔法师，已经辨认出了箱子上的全部 $N$ 种咒语类型，但并不知道需要解除咒语的正确顺序。 为了打开箱子，Lulu 尝试了如下操作过程： 1. Lulu 在剩余的 $N$ 个咒语中选择一个还未解除的咒语并尝试解除。当尝试解除第 $i$ 种咒语时，需要消耗 $M_i$ 点魔法力。 2. 如果她尝试解除的咒语正好是此时应当解除的那一个，则解除成功；否则，箱子会恢复到最初的状态（所有 $N$ 个咒语都恢复），Lulu 可以立刻得知刚才是否解除了正确的咒语。所需的解除顺序始终不变。 3. 当所有 $N$ 个咒语都被按顺序成功解除后，箱子就会打开。 给定 $N$ 及每个咒语消耗的魔法力 $M_i$，请计算 Lulu 若使用最优策略打开箱子时，期望总共消耗的魔法力是多少。正确的解除顺序有 $N!$ 种可能，并且这些顺序都是等概率的。

输入从标准输入给出，格式如下： > $N$ $M_1$ $M_2$ $\dots$ $M_N$

输出 Lulu 期望消耗的总魔法力。允许的绝对误差或相对误差不超过 $10^{-6}$。

### 数据范围 - $1 \leq N \leq 100\,000$ - $1 \leq M_i \leq 100\,000$ - 所有输入数字均为整数。 由 ChatGPT 5 翻译