냉장 진열대의 기준 온도

문제

한 편의점은 냉장 진열대에 설치한 센서의 기록을 모아 점검 보고서를 만든다. 센서는 온도를 일정한 단위의 정수로 기록한다. 문이 열리거나 센서가 흔들리면 실제 보관 상태와 관계없는 값이 기록될 수 있으므로, 담당자는 정해진 절차에 따라 기록을 걸러 낸다. 먼저 각 기록이 장비의 유효 범위에 들어가는지 확인한다. 유효 범위의 최솟값은 L이고 최댓값은 R이다. 값이 L 이상 R 이하인 기록만 유효한 기록으로 남기며, 나머지는 범위 밖 기록으로 분류한다. 같은 값이 여러 번 기록되었더라도 각 기록은 별개로 취급한다. 다음으로 유효한 기록을 값의 오름차순으로 정렬하여 기준 온도를 정한다. 유효한 기록이 M개라면, 정렬한 결과에서 앞에서부터 ⌊(M+1)/2⌋번째 값을 기준 온도로 삼는다. 따라서 M이 짝수이면 가운데 두 값 중 작은 값이 기준 온도가 된다. 이때 순서는 1부터 센다. 기준 온도가 정해지면 유효한 기록 중 기준 온도와의 차이의 절댓값이 K보다 큰 기록을 이상치로 분류한다. 차이가 정확히 K인 기록은 이상치가 아니다. 이상치를 찾은 뒤 기준 온도를 다시 계산하거나 같은 절차를 반복하지 않는다. 범위 밖 기록은 이 단계에 참여하지 않으며 이상치 개수에도 포함하지 않는다. 보고서에는 기준 온도, 범위 밖 기록의 개수, 이상치의 개수를 차례로 적는다. 유효한 기록이 하나도 없으면 기준 온도를 정할 수 없으므로 숫자 대신 EMPTY를 적는다. 이 경우 이상치 개수는 0이다. 주어진 기록으로 보고서의 한 줄을 완성하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, L, R, K가 공백으로 주어진다. 1≤N≤50,000, -1,000≤L≤R≤1,000, 0≤K≤2,000이다.
둘째 줄에 N개의 정수 센서 값이 공백으로 주어진다. 각 값은 -1,000 이상 1,000 이하이다.

출력

기준 온도, 범위 밖 기록 개수, 이상치 개수를 공백으로 구분하여 한 줄에 출력한다. 유효한 기록이 없으면 첫 번째 항목으로 EMPTY를 출력한다.

7 0 10 2
-1 2 3 3 7 10 11

3 2 2

3 0 5 0
-2 8 9

EMPTY 3 0

4 -5 5 0
1 1 2 2

1 0 2

출처: Devin.KR 자체 제작