P0678

[Baltic2007]Sound静音问题

[Baltic2007]Sound静音问题

在数字录音中，声音可以用表示空气压力的一串数字描述，序列中的每个值称为一个采样，采样之间的时间间隔相同。许多声音处理任务需要将录制的声音分成若干段由静音隔开的非静音片段。为了避免划分出过多或过少的非静音片段，通常将连续的 mm 个采样定义为静音，当且仅当这段序列中采样的最大值与最小值之差不超过给定的阈值 cc。

请编写程序，检测给定的 nn 个采样中的所有静音片段。

输入格式

第一行包含三个整数 nn、mm 和 cc，分别表示采样总数、静音片段的长度，以及静音片段中允许的最大噪音程度。

第二行包含 nn 个整数 aia_i，表示声音的各个采样值，相邻整数之间用空格分隔。

输出格式

按出现的先后顺序输出所有静音片段的起始位置 ii。其中，ii 满足：

max⁡(ai,…,ai+m−1)−min⁡(ai,…,ai+m−1)≤c。\max(a_i,\ldots,a_{i+m-1})-\min(a_i,\ldots,a_{i+m-1})\le c。

每行输出一个静音片段的起始位置。

如果不存在静音片段，则输出 NONE。

样例输入

7 2 0
0 1 1 2 3 2 2

样例输出

2
6

数据范围

  • 1≤n≤1061\le n\le 10^6；
  • 1≤m≤1041\le m\le 10^4；
  • 0≤c≤1040\le c\le 10^4；
  • 0≤ai≤1060\le a_i\le 10^6。

来源与许可

本题为 Baltic 2007 试题「Sound」，题面与测试数据整理自 BZOJ 1342。

样例 1

输入

7 2 0
0 1 1 2 3 2 2

输出

2
6