서가 센서의 이상 구간

문제

도서관의 서가에는 주변 상태를 일정한 간격으로 측정하는 센서가 설치되어 있다. 센서에서 수집한 N개의 원본 측정값이 시간순으로 저장되어 있다. 데이터 담당자는 갑작스러운 변화를 찾아 점검할 구간을 정하려 한다. 각 측정값의 위치는 먼저 수집한 값부터 1번, 2번, …, N번이다. 판정에 사용하는 기준 길이는 K이고 허용 차이는 T이다. 처음 K개의 값은 비교할 과거 기록이 충분하지 않으므로 이상 여부를 판정하지 않는다. K보다 큰 위치 i에서는 바로 앞 K개 원본 측정값, 즉 i-K번부터 i-1번까지의 산술평균을 구한다. i번 측정값과 이 평균의 차이의 절댓값이 T보다 엄격하게 크면 i번을 이상 위치로 판정한다. 차이가 정확히 T이면 이상 위치가 아니다. 평균을 정수로 반올림하거나 버리지 않고 정확한 값으로 비교한다. 한번 이상 위치로 판정된 값도 이후 평균을 계산할 때 그대로 포함한다. 값을 제거하거나 정상값으로 바꾸지 않으며, 모든 판정은 처음 주어진 원본 기록에만 의존한다. 따라서 특정 위치의 판정 결과가 뒤쪽 위치의 비교 대상 개수를 바꾸는 일은 없다. 담당자는 이상 위치의 총개수와 함께 이상이 끊기지 않고 이어진 가장 긴 구간을 보고하려 한다. 연속 구간은 위치 번호가 하나씩 증가하면서 그 안의 모든 위치가 이상 위치인 구간이다. 판정하지 않은 처음 K개 위치는 이상 구간에 포함할 수 없다. 가장 긴 구간이 여러 개이면 시작 위치가 가장 작은 구간을 선택한다. 이상 위치가 하나도 없으면 총개수, 구간 길이, 시작 위치를 모두 0으로 보고한다. 주어진 기록을 분석하여 이 세 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, K, T가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ K ≤ N, 0 ≤ T ≤ 1,000이다.
둘째 줄에 시간순 측정값을 나타내는 정수 x_1, x_2, …, x_N이 공백으로 구분되어 주어진다. 모든 i에 대하여 0 ≤ x_i ≤ 1,000이다.

출력

이상 위치의 총개수, 선택한 연속 구간의 길이, 그 구간의 시작 위치를 순서대로 한 줄에 공백으로 구분하여 출력한다. 시작 위치는 1부터 센다. 이상 위치가 없으면 0 0 0을 출력한다.

7 2 3
10 10 15 14 10 30 30

4 3 5

4 1 0
8 8 8 8

0 0 0

5 1 2
0 5 5 0 0

2 1 2

출처: Devin.KR 자체 제작