침묵 구간 찾기

디지털 음악에서 소리는 일정한 시간 간격마다 측정한 대기압 변화 값들의 나열로 표현된다. 이렇게 한 시점에서 측정한 값을 샘플이라고 한다.

녹음된 소리를 처리할 때, 연속한 m개의 샘플에서 최댓값과 최솟값의 차이가 c 이하인 구간을 침묵 구간으로 본다.

n개의 샘플로 이루어진 녹음과 m, c가 주어질 때, 모든 침묵 구간의 시작 위치를 찾으시오. 위치는 1부터 센다.

첫째 줄에 세 정수 n, m, c가 주어진다.

• 1 <= n <= 1,000,000
• 1 <= m <= 10,000
• 0 <= c <= 10,000

둘째 줄에는 각 샘플의 값인 정수 a_i가 n개 주어진다.

• 0 <= a_i <= 1,000,000 (1 <= i <= n)

다음 조건을 만족하는 모든 시작 위치 i를 오름차순으로 한 줄에 하나씩 출력한다.

max(a[i], ..., a[i+m-1]) - min(a[i], ..., a[i+m-1]) <= c

침묵 구간이 하나도 없다면 NONE을 출력한다.