천문대 센서의 경고 구간

문제

천문대의 관측 장비에는 주변 밝기를 일정한 간격으로 측정하는 센서가 달려 있다. 센서는 밝기를 0부터 100까지의 정수로 기록한다. 장비 담당자는 갑자기 달라진 측정값을 후속 분석에서 구별할 수 있도록 원본 기록에 이상치 표시를 붙이려고 한다. 측정값을 삭제하거나 바꾸는 대신, 각 기록이 정해진 비교 규칙을 만족하는지 검사한다. 시간순으로 기록된 측정값을 a_1부터 a_N까지라 하고, 비교에 사용할 과거 기록의 개수를 W라 한다. 처음 W개의 기록은 비교를 준비하는 구간이다. 이 기록들은 값과 관계없이 이상치로 표시하지 않는다. 이후의 i번째 기록은 바로 앞 W개의 원본 측정값, 즉 a_(i-W)부터 a_(i-1)까지의 산술평균과 비교한다. 현재 측정값 a_i는 자신의 비교 평균에 포함하지 않는다. 현재 측정값과 비교 평균의 차이의 절댓값이 D보다 크면 해당 기록을 이상치로 표시한다. 차이가 정확히 D이면 정상으로 처리한다. 평균을 정수로 버리거나 반올림하지 않으며, 주어진 수들의 정확한 평균을 기준으로 판정한다. 과거 기록이 이미 이상치로 표시되었더라도 이후 평균 계산에는 그 원본 값을 그대로 포함한다. 이상치 표시가 비교 대상의 개수나 다음 기록의 판정 규칙을 바꾸지는 않는다. 담당자는 표시된 기록의 총개수와 함께, 이상치가 가장 오래 연속된 구간을 확인하려고 한다. 연속 구간은 시간상 이웃한 기록들이 모두 이상치로 표시된 구간이다. 중간에 정상 기록이 하나라도 있으면 서로 다른 구간으로 나뉜다. 구간의 길이는 그 구간에 포함된 기록의 개수이며, 실제 시간으로 환산하지 않는다. 가장 긴 구간이 여러 개라면 시작 기록 번호가 가장 작은 구간을 선택한다. 전체 기록을 검사하여 이상치의 총개수, 선택한 연속 구간의 시작 번호, 그 길이를 구한다. 기록 번호는 1부터 시작한다. 이상치가 하나도 없으면 선택할 연속 구간이 없으므로 세 값을 모두 0으로 출력한다. W가 N과 같으면 모든 기록이 준비 구간에 속하므로 이 경우에도 이상치는 없다.

입력

첫째 줄에 세 정수 N, W, D가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 60,000, 1 ≤ W ≤ N, 0 ≤ D ≤ 100이다.
둘째 줄에 시간순 측정값 a_1, a_2, …, a_N이 공백으로 구분되어 주어진다. 모든 a_i는 0 이상 100 이하의 정수다.

출력

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

8 2 10
10 10 40 40 10 10 40 40

6 3 6

7 2 20
0 0 20 0 100 0 100

3 5 3

4 4 0
3 100 0 7

0 0 0

출처: Devin.KR 자체 제작