시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 136 40 34 29.310%

문제

디지털 음악에서 소리는 대기압의 변화를 나타내는 숫자로 표현한다. 대기압의 변화는 일정한 시간 구간을 정해놓고, 연속되는 구간동안 얼마나 빠르게 변했는지를 측정한다. 이렇게 측정한 값을 샘플이라고 한다.

음성 처리에서 가장 중요한 단계는 녹음된 소리를 사일런스 기준으로 사일런스가 아닌 구간으로 나누는 작업이다. 너무 많은 조각이 나는 것을 방지 하기 위해서 사일런스는 최저값과 최고값의 차이가 c를 넘지않는 샘플 m개의 연속이라고 정의한다.

샘플 n개 이루어진 레코딩과 m과 c가 주어졌을 때, 사일런스를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 샘플의 수 n (1 <= n <= 1,000,000), m (1 <= m <= 10,000), c (0 <= c <= 10,000)가 주어진다.

둘째 줄에는 각 샘플의 값 ai가 주어진다. (0 <= ai <= 1,000,000 for 1 <= i <= n)

출력

max(a[i . . . i+m−1])−min(a[i . . . i+m−1]) <= c를 만족하는 모든 i를 오름차순으로 한 줄에 하나씩 출력한다.

만약, 주어진 입력에 사일런스가 없다면, NONE을 출력한다.

예제 입력

7 2 0
0 1 1 2 3 2 2

예제 출력

2
6

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 3번