Problem Description

You have $n$ piles of stones. The $i$-th pile contains $a_i$ stones. You will perform $n-1$ operations. In each operation, you may choose two piles and merge them into one pile. The score gained is the sum of the sizes of the two chosen piles.

Now, if in each operation you randomly choose two piles to merge, what is the expected total score?

Input Format

The first line contains a positive integer $n$.

The next line contains $n$ numbers $a_i$.

Output Format

Output one real number in a single line, representing the answer.

An answer with an error not exceeding $10^{-6}$ will be considered correct.

5
3 1 2 6 3

38.5000000000

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $2 \le n \le 500$ and $1 \le a_i \le 10^9$.

Notes

Translated from AGM 2022 Qualification Round H Magic Powers。

Translated by ChatGPT 5