2374. The Sound of Silence

单点时限: 10.0 sec

内存限制: 256 MB

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.

输入格式

The first line of the file contains three integers: n (1 ≤n ≤1,000,000), the number of samples in the recording; m (1 ≤m ≤10,000), the required length of the silence; and c (0 ≤c ≤10,000), the maximal noise level allowed within silence.

The second line of the file contains n integers ai (0 ≤ai ≤1,000,000 for 1 ≤i ≤n), separated by single spaces: the samples in the recording.

输出格式

The output should list all values of i such that max(a[i . . . i+m-1])-min(a[i . . . i+m-1]) ≤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.

样例

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

25 人解决,27 人已尝试。

35 份提交通过,共有 112 份提交。

4.1 EMB 奖励。

创建: 15 年,5 月前.

修改: 5 年,1 月前.

最后提交: 1 月前.

来源: BOI 2007

题目标签