#1461. slecy

MCPlayer542 受不了他的两个 slecy 队友了。

来自 slecy 队友的手办已经堆满了机房的桌子，连放电脑加训的地方都没有，于是 MCPlayer542 打算把队友的手办全部打包贱卖 (危险行为，请勿模仿)。

MCPlayer542 一共打算处理 $n$ 个手办，编号为 $1,\ 2,\ \ldots,\ n$。MCPlayer542 把它们打包为若干编号连续的组，并分别卖出去。第 $i$ 个手办有一个 XP 值 $a_i$，而一组手办的价值则为其中最大的 XP 值减去最小的 XP 值—— XP 越为多样，其价值也就越高(确信)。同时，如果一组手办的数量少于 $m$，也会因为缺乏多样性而卖不出去。

因为MCPlayer542非常生气，因此他希望分组后，每组手办具有的最大价值最小。请你求出这个最小值。

形式化地，给一个长度为 $n$ 的整型数组 $a_i$，将数组划分为若干分别具有至少 $m$ 个元素的下标连续的段，每段的价值为该组中最大元素的值-最小元素的值，求最大价值最小是多少。

第一行两个正整数 $n,\ m$。

第二行 $n$ 个正整数 $a_1,\ a_2,\ \ldots,\ a_n$。

一行一个正整数，表示答案。

样例输入1

8 3
7 6 9 4 5 9 10 10

样例输出1

5

样例输入2

18 4
24 40 10 60 26 15 45 40 83 17 88 83 57 49 74 61 39 19

样例输出2

66

数据范围

$1\le m\le n\le 5\times10^5$

$1\le a_i\le 10^9$

提示

在样例 1 中，MCPlayer542 可以将前四个手办打包，价值为 $9-4=5$；将后四个手办打包，价值为 $10-5=5$，此时最大价值为 $5$。可以证明不存在比这更小的最大价值。