회의실 센서의 이웃 기록

문제

회의실의 환경 관리 장치는 회의가 진행되는 동안 센서 값을 모은다. 임베디드·데이터 담당자는 수집된 기록을 보고서에 반영하기 전에, 비슷한 값이 충분히 관측되었는지 확인하는 필터를 구현하려 한다. 센서 값은 장치가 정수로 변환한 값이며, 기록에는 수집된 순서대로 1번부터 N번까지 번호가 붙어 있다. 수집 간격은 이 필터의 판단에 사용하지 않는다. 필터에는 허용 차이 D와 최소 지지 개수 K가 설정되어 있다. i번 기록의 값이 A_i일 때, 전체 기록 중 값과 A_i의 차이의 절댓값이 D 이하인 기록을 i번 기록의 지지 기록이라고 한다. 즉, j번 기록은 |A_j-A_i|≤D를 만족할 때 지지 기록에 포함된다. 자기 자신도 지지 기록이며, 서로 다른 번호에 같은 값이 들어 있다면 각각 별개의 기록으로 센다. 따라서 지지 개수는 항상 1 이상이다. 각 기록의 지지 개수가 K 이상이면 정상 기록으로 분류하고, K보다 작으면 이상 기록으로 분류한다. 이 판단은 모든 기록에 대해 최초에 수집한 전체 데이터를 기준으로 한 번만 수행한다. 어떤 기록이 이상 기록으로 분류되더라도 다른 기록의 지지 개수를 계산할 때 제외하지 않는다. 또한 값이 비슷한 기록들을 연달아 연결할 수 있다는 이유만으로 모두 지지 기록이 되는 것은 아니다. 지지 여부는 반드시 판단 대상 기록과의 직접적인 값 차이로 결정한다. 이상 기록의 개수와 해당 기록들의 번호를 구하는 프로그램을 작성한다. 장치의 원래 수집 순서를 확인할 수 있도록 번호는 오름차순으로 출력한다. 값이 같은 기록도 각자의 번호로 출력하며, 이상 기록이 하나도 없다면 개수 0만 출력한다.

입력

첫째 줄에 정수 N, D, K가 공백으로 구분되어 주어진다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다.
제약은 1≤N≤100,000, 0≤D≤1,000,000,000, 1≤K≤N, 0≤A_i≤1,000,000,000이다.

출력

첫째 줄에 이상 기록의 개수 M을 출력한다. M이 1 이상이면 둘째 줄에 이상 기록의 번호 M개를 오름차순으로 공백으로 구분하여 출력한다. M이 0이면 둘째 줄을 출력하지 않는다.

8 2 3
20 22 21 40 42 70 42 90

2
6 8

5 0 2
7 7 12 4 12

1
4

4 5 1
0 100 200 300

0

출처: Devin.KR 자체 제작