Mountain Peaks — Min Difference With viewingGap

Choose a pair of peaks whose index distance is at least viewingGap, minimizing the absolute difference of their heights. A distance equal to viewingGap is allowed; when gap=1, any two distinct indices are allowed, so the wording "non-adjacent" in the original second example is inaccurate.

This site's standard input/output is stated explicitly.

输入格式

The first line contains n viewingGap, and the second line contains n heights. 2≤n≤100000, 1≤viewingGap<n, 1≤height[i]≤10⁹.

输出格式

Output one integer answer.

样例 1

输入：

5 3
1 5 4 10 9

输出：

4

样例 2

输入：

4 1
3 10 5 8

输出：

2

样例 3

输入：

3 2
7 2 7

输出：

0

样例说明

Example 1: the three allowed pairs have height differences 9, 8, and 4, so the minimum is 4. Example 2: 3 and 5, as well as 10 and 8, both differ by 2 with an index distance of at least 1, so the answer is 2. Example 3: the first and last positions are 2 apart and have the same height, so the answer is 0.