건조기 진동 기록 점검

문제

세탁소의 건조기에는 진동 센서가 달려 있다. 센서는 일정한 시간 간격으로 진동의 세기를 측정하고, 이를 0부터 9까지의 정수 등급으로 저장한다. 임베디드 장치에 저장된 기록을 넘겨받은 데이터 담당자는 순간적으로 진동이 달라진 구간을 찾아 점검 목록을 만들려고 한다. 기록은 측정된 순서대로 1번부터 N번까지 번호가 붙어 있다. 점검에는 기준 길이 K와 허용 차이 D를 사용한다. i번 기록을 판정할 때는 그 기록 바로 앞의 K개 기록, 즉 i-K번부터 i-1번까지의 산술평균을 기준값으로 삼는다. i번 값과 기준값의 차이의 절댓값이 D보다 엄격하게 크면 i번 기록을 이상치로 표시한다. 차이가 정확히 D이면 이상치가 아니다. 기준값은 소수일 수 있으며, 반올림하거나 버리지 않고 정확한 평균으로 비교한다. 앞에 K개의 기록이 없는 1번부터 K번까지의 기록은 판정하지 않으며 이상치로 표시하지 않는다. 또한 이상치로 표시된 값도 원래 측정값 그대로 남겨 둔다. 이후 기록의 기준값을 계산할 때 이상치를 제외하거나 다른 값으로 바꾸지 않는다. 따라서 각 기록의 판정은 항상 입력으로 주어진 원본 기록만을 사용한다. 담당자는 전체 이상치 개수와 함께, 이상치가 연속으로 나타난 가장 긴 구간을 확인하려고 한다. 연속 구간은 기록 번호가 끊기지 않고 이어지며, 그 안의 모든 기록이 이상치인 구간이다. 중간에 정상 기록이 하나라도 있으면 서로 다른 구간으로 나뉜다. 가장 긴 구간이 여러 개이면 시작 번호가 가장 작은 구간을 선택한다. 이상치가 하나도 없다면 선택할 구간이 없다고 처리한다. 주어진 기록에 대해 전체 이상치 개수, 선택한 구간의 길이, 선택한 구간의 시작 번호를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, K, D가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ K ≤ N, 0 ≤ D ≤ 9이다.
둘째 줄에 측정 순서대로 N개의 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ A_i ≤ 9이다.

출력

전체 이상치 개수, 가장 긴 연속 이상치 구간의 길이, 선택한 구간의 시작 번호를 순서대로 한 줄에 공백으로 구분하여 출력한다. 가장 긴 구간이 여러 개이면 시작 번호가 가장 작은 구간을 선택한다. 이상치가 없으면 0 0 0을 출력한다.

10 3 2
2 2 2 8 8 2 2 9 3 3

5 5 4

9 2 3
1 1 7 1 1 7 1 1 7

3 1 3

4 4 0
9 9 9 9

0 0 0

출처: Devin.KR 자체 제작