Average and median P67363


Statement
 

pdf   zip

html

Consider a set S = {x1, …, xk} of natural numbers (maybe with repetitions), with odd k. The average of S is defined as (∑1 ≤ i ≤ k xi)/k. The median of S is defined as the element that is in the middle of the set after we sort it. For instance, for S = { 1, 2, 2, 4, 5 }, the average is (1 + 2 + 2 + 4 + 5)/5 = 14/5 = 2.8, and the median is 2.

You are given a set of n natural numbers, with even n. Remove exactly one element so as to maximize the absolute value of the difference between the average and the median.

Input

Input consists of several cases, each one with an even n, followed by n natural numbers between 0 and 109. Assume 4 ≤ n ≤ 105.

Output

Print the maxim possible difference between the average and the median, with two digits after the decimal point. To do so, include these two lines at the beginning of your main: 

    cout.setf(ios::fixed);
    cout.precision(2);

The input cases do not have precision issues.

Public test cases

  • Input

    6  1 2 2 3 4 5
8  2 1 4 8 0 3 9 2
4  999999999 1000000000 999999998 999999998
4  0 1 2 9
4  0 7 8 9

    Output

    0.80
1.71
0.67
2.33
2.33
    • Information
    Author
    Félix Moreno
    Language
    English
    Official solutions
    C++
    User solutions
    C++