Three Numbers, Two Ms

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.

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.

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