AT_scpc2026_div2_e Opening Magical Box

#### 表示言語 / / ルルは宝物が入った魔法の箱を見つけた．箱には互いに異なる $ N $ 種類の魔法が $ 1 $ 回ずつかけられており，それらを正しい順序ですべて解除しなければ箱を開けることができない．天才魔法使いであるルルは，箱にかけられている $ N $ 種類の魔法の種類はすべて特定したが，解除すべき正しい順序は知らない． ルルは箱を開けるため，次の方法で箱を開けようとする． 1. ルルは $ N $ 種類の魔法のうち，まだ箱にかかっている魔法を $ 1 $ つ選び，解除を試みる． $ i $ 番目の魔法の解除を試みると， $ M_i $ の魔力が消費される． 2. 解除を試みた魔法が順序に合う魔法なら解除に成功する．順序に合わない魔法なら， $ N $ 種類の魔法がすべてかかった状態に戻る．解除の試みが成功したかどうかはすぐに分かる．解除に必要な魔法の順序は変わらない． 3. $ N $ 個の魔法がすべて解除されると箱が開く． $ N $ と各魔法の消費魔力 $ M_i $ が与えられる．ルルが最適な戦略で箱を開けるとき，消費する魔力の合計の期待値を求めよ．箱を開ける正しい魔法の順序は $ N! $ 通りのうちの $ 1 $ つであり，すべての順序が正解である確率は等しい．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M_1 $ $ M_2 $ $ \dots $ $ M_N $

ルルが消費する魔力の合計の期待値を出力せよ．絶対誤差または相対誤差は $ 10^{-6} $ まで許容される．

### Constraints - $ 1 \leq N \leq 100\,000 $ - $ 1 \leq M_i \leq 100\,000 $ - 入力される数値はすべて整数である．