Description

After entering the forbidden land, Facer meets an opponent.

More specifically, Facer's magic is a sequence of numbers.

However, Facer's ability is limited: this sequence can only be chosen from the given $n$ numbers, and the magic value produced equals the average of the chosen numbers.

His opponent does not wield magic as powerful as Facer's, but he can counter: he takes the median of the numbers Facer chose; that is his magic value.

Find the maximum amount by which Facer can counter the opponent's magic.

In one sentence: given $n$ numbers, you may choose any non-empty subset so that (average − median) is maximized.

Definition of median: for a multiset of size $k$, sort the chosen numbers in non-decreasing order. If $k$ is odd, the median is the middle element; if $k$ is even, the median is the average of the two middle elements.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ numbers as described.

Output Format

Output the maximum value of (average − median) that Facer can achieve, to two decimal places.

4
1 2 3 4

0.33

4
1 2 3 9

2.00

2
1 2

0.00

Hint

Constraints:

• For $20\%$ of the testdata, $n \leq 100$.
• For $50\%$ of the testdata, $n \leq 2000$.
• For $100\%$ of the testdata, $n \leq 10^5$, $0 \leq x_i \leq 10^6$.

Translated by ChatGPT 5