세 수, 두 M
시간 제한2초메모리 제한128 MB
정수 n개 중 세 개를 골라 (중앙값-평균)에 3을 곱한 값을 최대화하는 문제로, 정렬 후 최솟값과 최댓값을 이용해 계산합니다.
문제
정수 n개로 이루어진 수열 A[1], A[2], ..., A[n]이 주어진다.
서로 다른 세 인덱스 i, j, k를 골라 세 값 A[i], A[j], A[k]를 선택한다. 선택한 세 수를 정렬했을 때 가운데에 오는 값이 중위값이고, 세 수의 합을 3으로 나눈 값이 평균값이다.
세 수를 적절히 선택하여 중위값과 평균값의 차이가 최대가 되도록 하자.
입력
첫째 줄에 정수 n이 주어진다.
3 <= n <= 100,000
다음 n개의 줄에는 수열의 원소가 한 줄에 하나씩 주어진다. 각 원소의 절댓값은 100,000,000을 넘지 않는다.
출력
가능한 중위값과 평균값의 차이의 최댓값에 3을 곱한 값을 출력한다.