서가 사이의 센서 기록

문제

도서관의 임베디드 장치는 서가 사이에 설치된 센서에서 측정값을 모아 관리 서버로 보낸다. 데이터 담당자는 통신 과정에서 순간적으로 튄 값을 찾기 위해, 한 묶음의 기록에 동일한 기준값을 적용하려 한다. 각 기록에는 수신된 순서대로 1번부터 N번까지 번호가 붙어 있으며, 측정값은 음수를 포함할 수 있는 정수다. 기준값은 이 묶음의 측정값을 작은 순서대로 정렬했을 때 아래쪽 가운데에 놓이는 값으로 정한다. 정확히는 정렬한 값 중 1부터 세어 ⌊(N+1)/2⌋번째 값이다. 따라서 기록이 짝수 개이면 가운데 두 값 중 작은 값을 사용한다. 같은 측정값이 여러 번 나타나면 각각 별개의 기록으로 세며, 정렬하거나 기준값을 구하는 과정에서 중복을 제거하지 않는다. 허용 차이를 나타내는 음이 아닌 정수 D가 주어진다. 어떤 기록의 측정값을 x, 기준값을 b라고 할 때, |x-b|가 D보다 크면 그 기록을 이상치로 판정한다. 차이가 정확히 D인 기록은 정상이다. 이상치로 판정된 값도 처음 기준값을 계산할 때는 포함한다. 이상치를 제거한 뒤 기준값을 다시 계산하거나, 앞선 기록의 판정에 따라 다른 기록의 기준을 바꾸는 일은 없다. 담당자가 원본 기록과 판정 결과를 대조할 수 있도록 기준값과 이상치 개수를 출력하고, 이상치 기록의 원래 번호도 출력해야 한다. 번호는 측정값 순서가 아니라 원본에서의 번호가 증가하는 순서로 나열한다. 같은 측정값을 가진 여러 기록이 이상치라면 그 번호를 모두 포함한다. 이상치가 하나도 없다면 번호를 출력하는 줄에는 0 하나를 출력한다.

입력

첫째 줄에 기록 수 N과 허용 차이 D가 공백으로 주어진다. N은 1 이상 50,000 이하의 정수이고, D는 0 이상 10,000 이하의 정수다.
둘째 줄에 수신 순서대로 N개의 정수 측정값이 공백으로 주어진다. 각 측정값은 -999 이상 999 이하이다.

출력

첫째 줄에 기준값과 이상치 개수를 공백으로 구분하여 출력한다. 둘째 줄에 이상치 기록의 번호를 증가하는 순서로 공백으로 구분하여 출력한다. 이상치가 없으면 둘째 줄에 0을 출력한다.

6 3
8 2 5 5 -1 9

5 2
5 6

4 0
7 7 7 7

7 0
0

1 100
-8

-8 0
0

출처: Devin.KR 자체 제작