Three Numbers, Two Ms

Time limit2sMemory limit128 MB

Summary
Given n integers, pick three to maximize 3 times (median minus mean), which reduces to sorting and checking min/max extremes.
Level

Medium4 of 10

Topics
Sorting, Greedy, Math
Solved
No attempts yet

Problem

You are given a sequence of n integers, A[1], A[2], ..., A[n].

Choose three distinct indices i, j, and k, and take the three values A[i], A[j], and A[k]. The median is the middle value after sorting the three chosen numbers, and the mean is their sum divided by 3.

Choose the three numbers so that the difference between the median and the mean is as large as possible.

Input

The first line contains an integer n.

3 <= n <= 100,000

Each of the next n lines contains one element of the sequence. The absolute value of every element is at most 100,000,000.

Output

Print the maximum possible difference between the median and the mean, multiplied by 3.

Examples1

  1. Example 1

    Input
    5
100
234
430
120
489
    Expected output
    349