Description

Little E has $n$ kinds of food to choose from, and each kind of food can be eaten at most once. The $i$-th food has a tastiness value $a_i$. Eating a food with tastiness value $a_i$ increases Little E’s satisfaction by $a_i$.

However, Little E’s stomach has a limit. Each time he eats a food, his fullness increases by $1$.

Little E’s final comfort level is defined as the square of his satisfaction divided by his fullness. Your task is to find the maximum possible comfort level.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$.

Output Format

Output one real number in one line, representing the maximum comfort level. Your answer is considered correct if its relative error or absolute error is within $10^{-6}$ compared to the standard answer.

2
2 1

4.50

Hint

Hint

It is recommended to output at least $8$ significant digits.

Sample Explanation

It is easy to see that eating both kinds of food is optimal. The comfort level is $\frac{(2+1)^2}{2} = 4.5$.

Constraints

For $30\%$ of the testdata, $n, a_i \le 20$.

For $50\%$ of the testdata, $n, a_i \le 2000$.

For another $15\%$ of the testdata, all $a_i$ are equal.

For $100\%$ of the testdata, $1 \le n \le 3 \times 10^{5}$ and $1 \le a_i \le 10^6$.

Translated by ChatGPT 5