배식대 센서의 이전 기록

문제

학교 급식실의 임베디드 장치는 배식대 보온 설비의 센서 값을 일정한 간격으로 수집한다. 데이터 담당자는 갑자기 변한 값을 찾아 점검 목록을 만들려고 한다. 센서가 전송한 기록은 측정된 순서대로 보관되며, 각 기록에는 1번부터 N번까지 번호가 붙는다. 모든 센서 값은 정수다. 점검에는 비교 길이 K와 허용 차이 T를 사용한다. 번호 i가 K보다 클 때, i번 기록의 기준값은 바로 앞에 있는 K개 기록, 즉 i-K번부터 i-1번까지의 센서 값의 산술평균이다. 현재 값과 기준값의 차이의 절댓값이 T보다 엄격하게 크면 i번 기록을 이상 기록으로 분류한다. 차이가 정확히 T이면 정상 기록이다. 기준값은 정수가 아닐 수 있으며, 평균을 반올림하거나 버리지 않고 정확한 값으로 비교한다. 처음 K개 기록은 앞선 기록이 부족하므로 검사하지 않는다. 이 기록들은 점검 목록에 들어가지 않지만 이후 기록의 기준값을 계산할 때는 사용된다. 또한 어떤 기록이 이상 기록으로 분류되더라도 원래 저장된 센서 값을 수정하거나 제거하지 않는다. 따라서 이후 기준값을 계산할 때 앞서 발견한 이상 기록의 값도 그대로 포함한다. 장치는 입력 전체를 한 번 전달한 뒤 점검 결과를 기다린다. 각 기록은 자신의 바로 앞 K개 기록하고만 비교하며, 자기 자신의 값이나 뒤에 있는 값은 기준값에 포함하지 않는다. N이 K와 같으면 검사할 기록이 하나도 없다. 이상 기록의 개수와 그 번호들을 시간 순서대로 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, K, T가 주어진다. 1≤K≤N≤20,000이고 0≤T≤999다. 둘째 줄에 정수 센서 값 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0≤A_i≤999다.

출력

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

7 3 2
10 10 10 13 11 10 20

2
4 7

4 2 1
4 4 5 5

0

1 1 0
0

0

출처: Devin.KR 자체 제작