자전거 센서의 기준 묶음

문제

공유 자전거의 정비 거치대에서는 자전거를 고정한 상태로 진동 센서의 값을 여러 번 읽는다. 임베디드 장치가 보낸 측정 묶음에는 정상적으로 수신한 값과 통신 실패 표시가 섞여 있다. 데이터 담당자는 이 묶음에서 기준값을 정한 뒤, 기준값에서 너무 멀리 떨어진 값을 제외하는 간단한 필터를 적용하려 한다. 측정 기록은 N개의 정수로 이루어진다. 값이 -1이면 통신 실패를 뜻하며 기준값 계산과 최종 집계에서 모두 제외한다. 0 이상 999 이하의 값은 정상적으로 수신한 값이다. 여기서 정상적으로 수신했다는 것은 통신에 성공했다는 뜻이며, 이후 필터에서 제외될 가능성은 여전히 있다. 특히 0은 유효한 측정값이므로 통신 실패와 구분해야 한다. 먼저 통신 실패를 제외한 모든 값을 오름차순으로 정렬한다. 남은 값이 M개라면, 정렬된 순서에서 1부터 세었을 때 ⌊(M+1)/2⌋번째 값을 기준값 C로 정한다. 즉 M이 홀수이면 가운데 값을 선택하고, M이 짝수이면 가운데 두 값 중 앞쪽 값을 선택한다. 같은 값이 여러 번 측정되었다면 각각을 별개의 기록으로 세며, 정렬할 때도 중복을 제거하지 않는다. 기준값을 정한 뒤에는 정상 수신 값 v 중에서 |v-C|가 주어진 허용 거리 D 이하인 기록만 남긴다. 기준값과의 차이가 정확히 D인 기록도 남긴다. 필터링은 이 기준값으로 단 한 번만 수행한다. 일부 기록을 제외한 뒤 기준값을 다시 계산하거나 필터를 반복해서 적용하지 않는다. 최종 보고서에는 기준값 C, 필터를 통과한 기록 수 K, 통과한 값의 합 S를 적는다. 통신 실패 기록은 K와 S에 포함하지 않으며, 같은 값이 여러 번 통과했다면 그 횟수만큼 개수와 합에 반영한다. 정상적으로 수신한 값이 하나도 없다면 기준값을 정할 수 없으므로 보고서에는 정해진 표시인 -1 0 0을 적는다.

입력

첫째 줄에 정수 N과 D가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 90,000이고 0 ≤ D ≤ 999이다.
둘째 줄에 N개의 정수 v_1, v_2, ..., v_N이 공백으로 구분되어 주어진다. 각 값은 -1 이상 999 이하이다.

출력

기준값 C, 필터를 통과한 기록 수 K, 통과한 값의 합 S를 공백으로 구분하여 한 줄에 출력한다. 정상 수신 값이 하나도 없으면 `-1 0 0`을 출력한다.

7 2
10 12 -1 11 90 9 13

11 5 55

3 999
-1 -1 -1

-1 0 0

4 0
0 999 999 0

0 2 0

출처: Devin.KR 자체 제작