Finding Silent Intervals

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.

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

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.