3358 - Sound 静音问题

通过次数

4

提交次数

18

时间限制 : 1 秒
内存限制 : 512 MB

数字录音中,声音是用表示空气压力的数字序列描述的,序列中的每个值称为一个采样,每个采样之间间隔一 定的时间。
很多声音处理任务都需要将录到的声音分成由静音隔开的几段非静音段。为了避免分成过多或者过少的非静音 段,静音通常是这样定义的:m 个采样的序列,该序列中采样的最大值和最小值之差不超过一个特定的阈值c。
请你写一个程序,检测 n 个采样中的静音。

输入

第一行有三个整数 n,m,c( 1 ≤ n ≤ 10^6 ,1 ≤ m ≤ 10^4 ,0 ≤ c ≤ 10^4 ),分别表示总的采样数、静音的 长度和静音中允许的最大噪音程度。
第 2 行 n 个整数 ai( 0 ≤ ai ≤ 10^6 ),表示声音的每个采样值,每两个整数之间用空格隔开。

输出

列出了所有静音的起始位置 i(i 满足max {ai ,ai+1 ⋯ ai+m−1} − min{ai ,ai+1 ⋯ ai+m−1} ≤ c ),每行表示 一段静音的起始位置,按照出现的先后顺序输出。如果没有静音则输出 NONE。

样例

输入

7 2 0
0 1 1 2 3 2 2

输出

2
6