P2797 Facer's Magic

Facer accidentally trespassed into a forbidden land and learned magic.

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.

The first line contains a positive integer $n$. The second line contains $n$ numbers as described.

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

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