题目描述

你已经做了 blg 出的 $8$ 道烂题了，他已经被你骂惨惨了，但没关系，他脸皮变厚了，坚持要出 $n$ 道烂题。

假定 blg 出了 $n$ 个题目，并打算将其全部用于 $m$ 场比赛中。很显然，同一道题目不会出现在不同的比赛中。

第 $i$ 个题目的思维难度为 $a_i$ 。为了方便整理试卷，同一场比赛只能用连续编号的题。

如果我们将第 $l$ 道题至第 $r$ 道题放到第 $j$ 场比赛，则第 $j$ 场比赛中题目的难度跨度为 $b_j=max(a_l...a_r)-min(a_l...a_r)$ 。

例如，第 $j$ 场比赛使用第 $l\sim r$ 题，假定 $a_{l\sim r}=[1,3,5,7,8,6,4,2]$ ，那么本场比赛的难度跨度为 $b_j=8-1=7$ 。

为了避免某一场比赛难度跨度太大，blg 的目标是合理将这些题目分配到 $m$ 场比赛中，使得所有的 $m$ 场比赛中，难度跨度最大的一场比赛的难度跨度尽量小。即找出所有的题目分配方案中，对 $j∈1...m$ ， $max(b_j)$ 最小的一种方案。

注意，同一场比赛必须使用连续的题目，且所有的题目都必须恰好被使用一次。

输入格式

第一行是两个整数 $n$ 和 $m$ 。

接下来一行有 $n$ 个数字，第 $i$ 个数字表示第 $i$ 题的思维难度 $a_i$ 。

一个数字，表示最优安排下，难度跨度的最大值。

5 2
3 2 4 5 4

7 3
1 3 1 4 5 2 1

6 3
1 8 11 18 21 28

样例1中，把前两个题目分到一组，后三个题目分到一组。难度跨度分别为 $1$ 和 $1$ ，两个组的难度跨度最大值即为 $1$ 。其他的分法难度跨度的最大值都大于 $1$ 。

样例2中，前三个题目一组，接下来两个题目一组，最后两个题目一组。难度跨度最大值为 $2$ 。

样例3中，每两个题一组，难度跨度都为 $7$ 。

对 $30\%$ 的数据， $1≤m≤n≤20$ 。

对 $100\%$ 的数据， $1≤m≤n≤2×10^5$ ， $1≤a_i≤10^9$ 。