Hide

Problem D
The Sound of Silence

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 treshold $c$.

Write a program to detect silence in a given recording of $n$ samples according to the given parameter values $m$ and $c$.

Input

The first line of the input 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 input 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.

Output

You should output a list of all values of $i$ such that $\max (a[i \dots i + m - 1]) - min(a[i \dots i + m - 1]) \le c$ (where $a[i \dots j]$ means the values $a[i], a[i + 1], \dots , a[j]$). 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.

Sample Input 1 Sample Output 1
7 2 0
0 1 1 2 3 2 2
2
6

Please log in to submit a solution to this problem

Log in