주문량 이상치 걸러내기

문제

온라인 쇼핑몰의 주문 집계 장치는 일정 간격마다 측정한 주문량 x_1, x_2, ..., x_N 을 순서대로 받는다. 장치는 최근에 정상으로 판정된 값 W개를 보관하는 창을 유지하며, 다음 규칙으로 이상치를 걸러낸다. 처음 W개의 측정값은 무조건 정상으로 보고 순서대로 창에 넣는다. 그 이후 i번째 측정값(W < i ≤ N)이 들어오면 현재 창에 있는 W개 값의 중앙값 m을 구한다. 중앙값은 값을 오름차순으로 정렬했을 때 ceil(W/2)번째 값이다. W가 짝수이면 두 중앙 후보 중 작은 쪽이다. |x_i - m| > K 이면 x_i를 이상치로 판정하고 창에는 넣지 않는다. 그렇지 않으면 x_i를 정상으로 보고 창에 넣으며, 창에서 가장 오래전에 들어온 값 하나를 뺀다. 같은 값이 여럿 있어도 각각 별개의 값으로 센다. 이상치로 판정된 측정값의 개수와, 이상치로 판정된 측정값의 번호(1부터 시작)를 작은 것부터 모두 구한다.

입력

첫 줄에 N, W, K가 공백으로 주어진다 (1 ≤ W ≤ N ≤ 40,000, 0 ≤ K ≤ 10^9). 둘째 줄에 x_1, ..., x_N 이 공백으로 주어진다 (-10^9 ≤ x_i ≤ 10^9). 모든 값은 정수이다.

출력

한 줄에 이상치의 개수를 먼저 출력하고, 이어서 이상치로 판정된 측정값의 번호를 오름차순으로 공백으로 구분해 출력한다. 이상치가 없으면 0만 출력한다.

8 3 2
10 11 50 12 9 13 -20 11

2 5 7

4 2 0
5 5 5 6

1 4

3 3 0
1 100 -5

0

출처: Devin.KR 자체 제작