Facer's Magic Duel

Facer has intruded into a forbidden area, where he encounters a rival. Facer's magic is expressed as a sequence of numbers. However, due to his limited ability, he can only choose a subset from a given set of \( n \) numbers, and his magic value is defined as the average of the numbers he selects.

His opponent, though not as powerful, knows how to counter Facer's move: he takes the selected numbers and computes their median. The opponent's magic value is this median.

Your task is to help Facer maximize the difference by which his magic overpowers his opponent's magic. In other words, you need to choose a nonempty subset (with at least two numbers so that the median is well-defined) from the \( n \) numbers such that the quantity \[ \text{Difference} = \text{Average} - \text{Median} \] is maximized.

Note: For a subset \( S \) of size \( k \) with elements sorted in non-decreasing order \( s_1, s_2, \dots, s_k \), assume the median is defined as \( s_{\lfloor (k+1)/2 \rfloor} \). It can be shown that the optimal strategy is to choose exactly two numbers: the smallest and the largest among the available numbers. Thus, the maximum difference is exactly \[ \frac{\max - \min}{2}. \]

inputFormat

The first line contains an integer \( n \) (\( 2 \le n \le 10^5 \)), representing the number of available numbers.

The second line contains \( n \) space-separated integers. Each integer will be in the range \( [-10^9, 10^9] \).

outputFormat

Output a single real number representing the maximum difference by which Facer can overpower his opponent. The answer is computed as \( \frac{\max - \min}{2} \).

sample

2
1 2

0.5