지원실 센서 기록 정제

문제

사내 IT 지원실은 직원에게 대여한 소형 장치가 과열되는지 확인하기 위해 센서 기록을 모은다. 장치는 측정값을 정수로 전송하지만, 연결이 불안정하면 센서의 정상 측정 범위를 벗어난 값이 기록되기도 한다. 정상 범위 안에 있더라도 다른 기록과 지나치게 동떨어진 값은 지원 담당자의 요약 보고서에서 제외하려 한다. 이번 보고서에서는 모든 기록에 같은 두 단계의 정제 규칙을 적용한다. 먼저 정상 범위의 양 끝값 L과 R을 사용한다. 측정값이 L 이상 R 이하이면 후보로 남기고, 그렇지 않으면 즉시 제외한다. 경계값 L 또는 R과 같은 측정값은 후보에 포함한다. 후보가 하나도 없으면 대표값을 정할 수 없으므로 두 번째 단계는 수행하지 않는다. 후보가 있으면 후보의 값들을 오름차순으로 정렬하여 대표값 M을 정한다. 후보 수를 K라고 할 때, M은 정렬된 후보 중 앞에서부터 세어 (K+1)을 2로 나눈 몫 번째에 있는 값이다. 위치는 1번부터 센다. 따라서 후보 수가 짝수이면 가운데 두 값 중 작은 값을 선택하며, 두 값의 평균을 계산하지 않는다. 두 번째 단계에서는 음이 아닌 정수 D를 사용한다. 각 후보의 값과 M의 차이의 절댓값이 D 이하이면 그 기록을 최종적으로 남긴다. 차이의 절댓값이 D보다 크면 이상치로 보고 제외한다. 대표값 M은 첫 번째 단계의 후보 전체로 한 번만 계산한다. 이상치를 제외한 뒤 대표값을 다시 계산하거나 정제 과정을 반복하지 않는다. 같은 측정값이 여러 번 등장하면 각각 독립적인 기록으로 취급한다. 예를 들어 같은 값의 기록 세 개가 조건을 만족하면 최종 기록 수는 세 개 늘어나고, 합계에도 그 값이 세 번 더해진다. 입력된 순서는 대표값이나 정제 결과에 영향을 주지 않는다. 지원 보고서에 사용할 대표값 M, 최종적으로 남은 기록 수, 그 기록들의 값의 합을 구한다.

입력

첫째 줄에 정수 N, L, R, D가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 60,000, -999 ≤ L ≤ R ≤ 999, 0 ≤ D ≤ 1,998이다.
둘째 줄에 N개의 정수 측정값이 공백으로 구분되어 주어진다. 각 측정값은 -999 이상 999 이하다.

출력

첫 번째 단계에서 후보가 하나도 남지 않으면 EMPTY를 출력한다. 그렇지 않으면 대표값 M, 최종적으로 남은 기록 수, 최종 기록의 값의 합을 공백으로 구분하여 한 줄에 출력한다. 합은 음수일 수 있다.

7 0 100 10
10 12 13 90 -5 14 200

13 4 49

3 20 30 0
-1 19 31

EMPTY

4 -10 10 0
2 2 8 8

2 2 4

출처: Devin.KR 자체 제작