AT_scpc2026_div2_e.Opening Magical Box

Lulu found a magical box containing treasure. The box has $N$ distinct spells cast on it, one of each type, and it can be opened only by dispelling all of them in the correct order. Lulu, a genius magician, has identified all $N$ types of spells on the box, but does not know the correct order in which they must be dispelled.

To open the box, Lulu attempts the following procedure.

1. Lulu chooses one spell that is still cast on the box among the $N$ spells and tries to dispel it. When Lulu tries to dispel the $i$-th spell, $M_i$ magic power is consumed.

2. If the attempted spell is the correct spell in the order, the dispelling succeeds. If it is not the correct spell in the order, the box returns to the state where all $N$ spells are cast on it. Lulu can immediately tell whether the dispelling attempt succeeded. The order required for dispelling the spells does not change.

3. Once all $N$ spells are dispelled, the box opens.

Given $N$ and the magic power cost $M_i$ of each spell, find the expected total amount of magic power Lulu will consume if Lulu opens the box using an optimal strategy. The correct order of spells is one of the $N!$ possible orders, and all possible orders are equally likely.

露露发现了一个装有宝藏的魔法宝箱。宝箱上施加了 $N$ 种互不相同的咒语，每种各一个，且只有按正确顺序逐一解除全部咒语，宝箱才能打开。露露是一位天才魔法师，已识别出宝箱上的全部 $N$ 种咒语类型，但尚不清楚它们必须被解除的正确顺序。

为打开宝箱，露露采用如下尝试过程：

1. 露露从当前仍作用于宝箱的 $N$ 个咒语中任选一个，尝试将其解除。当露露尝试解除第 $i$ 个咒语时，消耗 $M_i$ 点魔法值。

2. 若所选咒语恰好是当前所需解除的正确咒语（即处于正确顺序中的当前位置），则解除成功；否则，宝箱将重置回初始状态——即所有 $N$ 个咒语均重新施加于宝箱之上。露露能立即判断此次解除尝试是否成功。而咒语需被解除的正确顺序本身始终保持不变。

3. 当全部 $N$ 个咒语均被成功解除后，宝箱开启。

给定 $N$ 及每个咒语的魔法值消耗 $M_i$，求露露采用最优策略打开宝箱时，所消耗的魔法值总量的期望值。所有 $N!$ 种可能的正确咒语顺序等概率出现。

The input is given from Standard Input in the following format:

$N$
$M_1$ $M_2$ $\dots$ $M_N$

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

$N$
$M_1$ $M_2$ $\dots$ $M_N$

Output the expected total amount of magic power Lulu will consume. An absolute or relative error of at most $10^{-6}$ is accepted.

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

表示言語

/ /

Constraints

• $1 \leq N \leq 100\,000$
• $1 \leq M_i \leq 100\,000$
• All given numbers are integers.

表示语言

/ /

限制条件

• $1 \leq N \leq 100\,000$
• $1 \leq M_i \leq 100\,000$
• 所有给定的数均为整数。