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.

The input is given from Standard Input in the following format: > $ 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.

### Constraints - $ 1 \leq N \leq 100\,000 $ - $ 1 \leq M_i \leq 100\,000 $ - All given numbers are integers.