창고 센서의 기준값

문제

물류 창고의 자동 운반 통로에는 바닥의 진동을 측정하는 센서가 설치되어 있다. 임베디드 장치는 일정한 시간 간격으로 센서 값을 기록하고, 데이터 담당자는 한 묶음으로 수집한 기록에서 이상치를 표시한다. 운반 장비가 센서 바로 옆을 지나가면 일시적으로 큰 값이 기록될 수 있으므로, 기록 전체를 대표하는 기준값을 먼저 정한 뒤 각 기록을 검사한다. 한 묶음에는 시간순으로 N개의 센서 값이 들어 있다. 각 값은 0 이상 99 이하의 정수이며, 입력된 순서대로 1번부터 N번까지 번호를 붙인다. 같은 값이 여러 번 기록되어도 각각 별개의 기록으로 취급한다. 기록이 누락되는 경우는 없다. 기준값은 모든 센서 값을 오름차순으로 정렬했을 때 앞에서 ⌊(N+1)/2⌋번째에 있는 값이다. 여기서 ⌊x⌋는 x 이하인 가장 큰 정수이다. 따라서 N이 짝수이면 가운데 두 값 중 작은 값을 기준값으로 선택한다. 정렬은 기준값을 구하기 위한 절차이며, 각 기록의 번호는 처음 입력된 순서를 유지한다. 허용 차이 D가 주어진다. 어떤 기록의 센서 값과 기준값의 차이에 절댓값을 취한 결과가 D보다 크면 그 기록을 이상치로 판정한다. 차이가 정확히 D인 기록은 정상이다. 이상치로 판정한 기록을 제외하여 기준값을 다시 구하지 않으며, 처음 정한 하나의 기준값으로 모든 기록을 검사한다. 데이터 담당자가 원본 기록에서 이상치를 바로 찾을 수 있도록 기준값, 이상치의 개수, 이상치인 기록의 번호를 출력하는 프로그램을 작성한다. 기록 번호는 값의 크기와 관계없이 오름차순으로 출력한다. 이상치가 하나도 없으면 번호 목록 대신 0을 출력한다.

입력

첫째 줄에 기록의 개수 N과 허용 차이 D가 공백으로 구분되어 주어진다. N과 D는 정수이며 1 ≤ N ≤ 100,000, 0 ≤ D ≤ 99이다.
둘째 줄에 시간순으로 기록된 N개의 센서 값 a₁, a₂, …, aₙ이 공백으로 구분되어 주어진다. 각 aᵢ는 0 이상 99 이하의 정수이다.

출력

첫째 줄에 기준값을 정수로 출력한다. 둘째 줄에 이상치의 개수를 출력한다. 셋째 줄에 이상치인 기록의 번호를 오름차순으로 공백으로 구분하여 출력한다. 이상치가 없으면 셋째 줄에 0을 출력한다.

8 3
12 13 70 11 14 80 12 15

13
2
3 6

6 0
4 4 5 5 6 6

5
4
1 2 5 6

1 0
99

99
0
0

출처: Devin.KR 자체 제작