2405번 - 세 수, 두 M

문제

n개의 정수 A[1], A[2], …, A[n]이 있다. 서로 다른 세 정수 i, j, k에 대해서 a = A[i], b = A[j], c = A[k]라 하자. 세 수의 중위(Median)값은 정렬했을 때 가운데에 오는 수가 된다. 세 수의 평균(Mean)값은 (a+b+c)÷3이 된다.

만약 세 수가 5, 2, 5라면 중위값은 5, 평균값은 4가 된다. 세 수가 2, 3, 1이라면 중위값은 2, 평균값도 2가 된다.

n개의 수들이 주어졌을 때, 위와 같이 세 수를 선택하여(i, j, k가 서로 다르도록) 중위값과 평균값의 차이가 최대가 되도록 해 보시오.

입력

첫째 줄에 정수 n(3 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 n개의 정수들이 주어진다. 각 수들의 절댓값은 100,000,000을 넘지 않는다.

출력

첫째 줄에 중위값과 평균값의 차이를 세 배 한 값을 출력한다.

제한

힌트