小慕正在开发一个魔法能量分析系统，系统中有一条由 n 颗能量水晶组成的能量链。每颗水晶都有一个整数的能量值，依次排列成一个整数数组 `a[1], a[2], ..., a[n]`。 为了评估能量链的稳定性，小慕需要提取所有长度恰好为 `d` 的进行分析。 对于每一段连续的 `d` 颗水晶，定义它的为：``。 其中 `max_value` 是该段水晶的最大能量值，`min_value` 是该段水晶的最小能量值。 小慕的任务是： 找出所有这些长度为 `d` 的连续水晶段的波动幅度中，最大的那个值，并输出它。
提示：带虚线的词点一下有通俗解释。
输入描述
* 第一行包含一个整数 `n` (1 <= n <= 10^3)，表示水晶链的长度。 * 第二行包含 `n` 个整数 `a[1], a[2], ..., a[n]` (-10^9 <= a\[i] <= 10^9)，表示每颗水晶的魔力值。 * 第三行包含一个整数 `d` (1 <= d <= n)，表示要分析的连续水晶段的长度。
输出描述
* 输出一个整数，表示所有长度为 `d` 的连续水晶段的波动幅度中的最大值。
示例
示例 1
输入
5 1 3 2 5 4 3
输出
3
说明：对于 `a = [1, 3, 2, 5, 4]` 且 `d = 3`，所有长度为 `3` 的连续水晶段及其波动幅度为： * `[1, 3, 2]` → max\_value = 3, min\_value = 1 → 波动幅度 = 3 - 1 = 2 * `[3, 2, 5]` → max\_value = 5, min\_value = 2 → 波动幅度 = 5 - 2 = 3 * `[2, 5, 4]` → max\_value = 5, min\_value = 2 → 波动幅度 = 5 - 2 = 3 最大波动幅度为 `3`，因此输出 `3`。
时间限制 1000 ms · 内存限制 128 MB