Baltic Olympiad in Informatics: 2007 Day 1, Problem 3
In digital recording, sound is described by a sequence of numbers representing the air pressure, measured at a rapid rate with a fixed time interval between successive measurements. Each value in the sequence is called a sample.
An important step in many voice-processing tasks is breaking the recorded sound into chunks of non-silence separated by silence. To avoid accidentally breaking the recording into too few or too many pieces, the silence is often defined as a sequence of ~m~ samples where the difference between the lowest and the highest value does not exceed a certain threshold ~c~.
Write a program to detect silence in a given recording of ~n~ samples according to the given parameter values ~m~ and ~c~.
The first line of the file contains three integers: ~n~ ~(1 \le n \le 1\,000\,000)~, the number of samples in the recording; ~m~ ~(1 \le m \le 10\,000)~, the required length of the silence; and ~c~ ~(0 \le c \le 10\,000)~, the maximal noise level allowed within silence.
The second line of the file contains ~n~ integers ~a_i~ ~(0 \le a_i \le 1\,000\,000~ for ~1 \le i \le n)~, separated by single spaces: the samples in the recording.
The output should list all values of ~i~ such that ~\max(a[i \dots i + m - 1]) - \min(a[i \dots i + m - 1]) \le c~. The values should be listed in increasing order, each on a separate line.
If there is no silence in the input, write
NONE on the first and only line of the output.
7 2 0 0 1 1 2 3 2 2