BOI7SOU - Sound

no tags 

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.

Input

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.

Output

The file 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 file, write NONE on the first and only line of the output file.

Example

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

hide comments
siddharth_0196: 2017-05-13 15:17:41

O(nlogn) gives TLE!

mrinal_aich: 2016-09-21 13:13:19

You may use hash-map and queue of STL in C++.

Adamos Ttofari: 2015-07-12 10:55:09

I can't get it... My solution passes the official test data and I get a WA here :(

eightnoteight: 2015-06-15 17:43:38

nice problem; did it using simple stl map

maniAC: 2014-08-04 23:18:14

O(nlogn) Sparse table got TLE. O(n) Deque got AC.

Master Wad7a: 2013-05-06 10:18:48

AC in O(n log n) , but used fast input and a BIT (which in these cases is much faster than segment tree) :THATS A HINT

Nikhil Garg: 2010-12-31 17:05:52

Time limit is too strict. My O(N) solution times out. Too much IO.

Edit : Got Ac after more optimizations but Official BOI solution times out ! Problem is strongly IO intensive.

Last edit: 2010-12-31 17:46:18
Dominik Kempa: 2010-11-04 22:44:47

@problem setter: did you add your own tests? My solution passes official testdata. WA here...

re: apology, my mistake on uploading test cases. fixed.

Last edit: 2010-11-05 02:06:48

Added by:Race with time
Date:2010-11-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Baltic Olympiad 2007