Finding Silent Intervals

Time limit1sMemory limit128 MB

Summary

Find every starting index of a length-m window in an array where the max minus min value is at most c, using a sliding window with monotonic deques.

Level: Medium4 of 10
Topics: Sliding window, Queue, Array
Solved: No attempts yet

Problem

In digital music, sound is represented as a sequence of numbers measuring changes in air pressure at regular time intervals. Each measured value is called a sample.

When processing a recording, a silent interval is defined as m consecutive samples whose maximum value and minimum value differ by at most c.

Given a recording of n samples and the values m and c, find every silent interval. Positions are counted from 1.

Input

The first line contains three integers n, m, and c.

1 <= n <= 1,000,000
1 <= m <= 10,000
0 <= c <= 10,000

The second line contains n integers a_i, the sample values.

0 <= a_i <= 1,000,000 for 1 <= i <= n

Output

Print every starting position i, in increasing order and one per line, such that

max(a[i], ..., a[i+m-1]) - min(a[i], ..., a[i+m-1]) <= c.

If there is no silent interval, print NONE.

Examples1

Example 1
Input
```
7 2 0
0 1 1 2 3 2 2
```
Expected output
```
2
6
```