충전 예약을 고르는 순서

문제

전기차 충전소는 충전기 한 대의 예약 신청을 모아 하루 일정을 확정하려고 한다. 신청마다 원하는 충전 시작 시각이 정해져 있으며, 모든 신청은 정확히 D분 동안 충전기를 사용한다. 시작 시각을 앞당기거나 늦출 수 없고, 충전을 중간에 끊을 수도 없다. 충전소는 서로 겹치지 않게 승인할 수 있는 신청 수의 최댓값을 구하려고 한다. 신청에는 입력에 등장한 순서대로 1번부터 N번까지 번호를 붙인다. i번 신청의 시작 시각이 S_i라면 이 신청이 사용하는 구간은 S_i 이상 S_i+D 미만인 시간이다. 따라서 어떤 신청이 끝나는 시각과 다른 신청이 시작하는 시각이 같으면 두 신청을 모두 승인할 수 있다. 충전기 정리나 차량 교체에 별도의 시간은 필요하지 않다. 최대로 승인할 수 있는 수가 같더라도 여러 승인 방법이 생길 수 있으므로, 충전소는 결과를 하나로 정하기 위한 규칙도 마련했다. 먼저 모든 신청을 시작 시각이 빠른 순서로 정렬하고, 시작 시각이 같으면 신청 번호가 작은 순서로 정렬한다. 이 정렬에서 앞선 신청의 순위를 더 작은 정수로 정한다. 승인한 신청들을 이 순위의 오름차순으로 나열했을 때 얻는 순위 수열을 그 일정의 비교 수열이라고 한다. 최대로 많은 신청을 승인하는 일정 중 비교 수열이 사전순으로 가장 작은 일정을 선택한다. 길이가 같은 두 수열의 사전순은 처음으로 다른 위치의 정수가 더 작은 수열이 앞서는 방식이다. 출력할 때는 선택한 신청들의 번호를 실제 충전 시작 순서로 나열한다. 같은 시각의 신청은 D가 양수이므로 둘 이상 함께 승인할 수 없다. 주어진 신청 목록에서 규칙에 맞는 승인 결과를 구하는 프로그램을 작성한다.

입력

첫째 줄에 신청 수 N과 공통 충전 시간 D가 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ D ≤ 1,000,000이다.
다음 N개 줄 중 i번째 줄에 i번 신청의 시작 시각 S_i가 주어진다. 0 ≤ S_i ≤ 1,000,000이다. 모든 입력값은 정수이다.

출력

첫째 줄에 승인할 수 있는 최대 신청 수 K를 출력한다. 둘째 줄에 규칙에 따라 선택한 신청 번호 K개를 충전 시작 순서대로 공백으로 구분하여 출력한다. 주어진 제약에서 K는 항상 1 이상이다.

6 4
5
0
4
8
4
12

4
2 3 4 6

4 3
7
7
7
7

1
1

5 5
9
1
6
11
16

4
2 3 4 5

출처: Devin.KR 자체 제작