解题思路

题目可以转化为：在最多进行 (k) 次清仓操作的前提下，希望剩余物资数量最少的货架上的物资数量尽可能大。由于不同货架上的物资种类各不相同，清仓一个连续区间相当于将该区间内所有货架上的物资全部搬走（数量变为0）。留下的物资种类必须大于 0（不能全搬光），且剩余物资中最少的那个货架上的物资数量要尽可能大。

这类“最大值最小/最小值最大”问题通常可以使用二分答案来求解。我们二分最终的答案 (x)，检查是否可以通过最多 (k) 次删除操作，使得剩余的所有货架上的物资数量都至少为 (x)，并且至少剩下一个货架上有物资。

检查过程：

1. 将所有数量小于 (x) 的位置视为“必须删除”的（用 0 表示），其他位置视为“可保留”的（用 1 表示）。

题目内容

你是一位仓库管理员，面前有一排共 $n$ 个货架，编号从左到右依次为 $1$ 到 $n$。第 $i$ 个货架上存有 $a_i$ 件某种物资，不同货架上的物资种类各不相同。

你可以进行最多 $k$ 次清仓操作。每次操作需要选择一个编号连续的货架区间，将该区间内所有货架上的物资全部搬走（物资数量变为 $0$）。在整个过程中，你必须保证每一次操作后仓库里仍至少存在一种物资（即至少有一个货架上还有物资）。

你希望经过这些操作之后，剩余物资中最少的那个货架上的物资数量尽可能大。请问这个最大可能的最小值是多少？

约束：

• 货架数量 $n$ 不超过 $10^5$。
• 操作次数 $k$ 不超过 $10^5$。
• 每个货架上的初始物资数量 $a_i$ 均为正整数，且不超过 $10^6$。

输入描述

第一行包含两个整数 $n$ 和 $k$，分别表示货架数量和最多可执行的清仓操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，依次表示从左到右每个货架上的初始物资数量。

输出描述

输出一个整数，表示在满足操作要求的前提下，剩余物资数量最少的货架所能达到的最大物资数量。

样例1

输入

3 0
10 5 8

输出

5

说明

操作次数 $k=0$，无法进行任何清仓操作。所有货架的物资必须保持原状，剩余物资中的最小值即为原始数组的最小值 $\min(10,5,8)=5$，无法变得更大。

样例2

输入

5 2
2 10 3 10 4

输出

10

说明

我们希望剩余货架的物资均至少为 $10$。查看初始数组，货架 $1,3,5$ 上的物资分别为 2、3、4，均小于 $10$，必须清零。 这些需要清零的货架分布在数组两端（编号 $1$ 到 $5$）。如果只进行一次清仓操作覆盖整个区间 $[1,5]$，会将所有货架清零，违反“每次操作后至少存在一种物资”的规则。因此最少需要 $2$ 次操作：例如第一次清空 $[1,1]$，保留后面的物资；第二次清空 $[3,5]$。 由于 $k=2$，刚好足够，操作后剩余货架 $2$ 和 $4$ 上的物资皆为 10，最小值达到 10。经二分验证，$10$ 为可行最大值。

样例3

输入

6 1
7 2 9 3 8 1

输出

7

说明

二分验证可得最大可达到的最小值为 $7$。 当目标值设为 $7$ 时，物资小于 $7$ 的货架有：编号 $2$（物资 2）、编号 $4$（物资 3）和编号 $6$（物资 1）。这些货架并未占满整个数组，可以用一次操作覆盖区间 $[2,6]$ 将它们全部清零，操作后货架 $1$ 上的 7 保留，最小值即为 $7$。 若将目标提高到 $8$，货架 $1$ 的 7 也需清零，此时需要清零的货架覆盖了从 $1$ 到 $6$ 的整个范围，一次操作会导致全空，至少需要两次操作，而 $k=1$ 无法满足。故答案为 $7$。

样例4

输入

1 5
100

输出

100

说明

只有一个货架，物资数量为 100。由于规则要求每次操作后仓库中至少保留一种物资，而唯一的货架一旦被清空就会违反规则，因此不能执行任何清仓操作。无论 $k$ 有多大，都无法改变货架上的物资，剩余物资的最小值也只能是 100。