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 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 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
tarun_28: 2020-01-28 14:19:10

window sliding algorithm

Last edit: 2020-01-28 14:19:49
nadstratosfer: 2019-12-02 00:37:05

TL gone full retard. -1 for this.

priyanshucode: 2019-10-03 07:39:36

use multiset!!!....

shahayush457: 2019-06-19 07:44:27

O(nlogn) solution tle without fast IO. Accepted with fast IO.

akashranjan28: 2017-06-25 16:31:06

solved using set.
Similar to ARRAYSUB, but use fast i/o for this

akt_1998: 2017-05-25 13:46:59

Priority Queue :)

shreyasid_15: 2017-05-25 13:07:35

AC in O(n). used deque :)

conquistador: 2017-05-13 21:28:26

use array instead of maps and set for keeping track of k -sized window

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++.


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