该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

日志分包

题目描述

给定一个长度为 $n$ 的数组 $a$。

你需要将整个数组按照原有顺序划分成若干个非空连续段，并且划分出的连续段数量不超过 $k$。

对于任意一个连续段 $[l,r]$，定义它的代价为：

令 $M=\max_{l\le i\le r}a_i,\ m=\min_{l\le i\le r}a_i$，则答案为

其中：

• $\max_{l\le i\le r} a_i$ 表示该连续段中的最大值；
• $\min_{l\le i\le r} a_i$ 表示该连续段中的最小值；
• $r-l+1$ 表示该连续段的长度。

现在，你希望所有连续段的代价中的最大值尽可能小。

请你输出这个最小值。

备注

连续段指的是数组中一段下标连续的元素。 例如，$[a_2,a_3,a_4]$ 是一个连续段，而 $[a_1,a_3]$ 不是连续段。

输入格式

第一行输入两个整数 $n,k$ ($1\le k\le n\le 2\times 10^5$)，表示数组长度和允许划分出的连续段数量上限。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$ ($0\le a_i\le 10^9$)，表示数组中的元素。

输出格式

输出一个整数，表示在将数组划分成不超过 $k$ 个非空连续段的前提下，所有连续段代价的最大值的最小可能值。

输入输出样例 #1

输入 #1

6 3
5 1 4 7 6 8

输出 #1

5

输入输出样例 #2

输入 #2

7 2
4 4 4 9 9 9 9

输出 #2

4

输入输出样例 #3

输入 #3

5 5
10 1 10 1 10

输出 #3

1

说明/提示

样例 1 说明：

一种可行的划分方式为：

• $[5]$，代价为 $(5-5)+1=1$
• $[1,4]$，代价为 $(4-1)+2=5$
• $[7,6,8]$，代价为 $(8-6)+3=5$

此时所有连续段代价的最大值为 $5$。

可以证明，不存在最大代价小于 $5$ 的划分方案，因此答案为 $5$。