在一个遥远的星球上,这颗星球上的果树非常奇特,同一条直线上的果树只会长出不同种类的水果。
有一天塔子哥乘飞船来到了这里,由于他的食物不多了,于是他决定在这颗星球上进行补给。他发现了一个 n 棵果树长成的直线,其中第 i 棵果树上有 ai 个第 i 种水果。
塔子哥想要品尝一部分这些独特的水果,现在塔子哥可以对这个水果序列进行最多 k 次操作,每次可选择一个连续的区间将其中的水果全部吃掉,但剩余的水果种类必须大于 0 。
塔子哥知道,这个星球上的水果都非常美味,每一种都有独特的口感和香味。塔子哥不想错过任何一种美味的水果,所以塔子哥希望在吃掉一些水果后,剩余水果中数量最少的那种尽可能多,以便在未来能够继续享用美味的水果。
现在问题来了:在上述情况下,剩余水果中数量最少的那种最多能有多少呢?
输入第一行为两个正整数 n 和 k ,分别表示果树的数量以及最多的操作次数。(1<=n<=105 ,0<=k<=105)
输入第二行为 n 个正整数,其中第 i 个数为 ai ,表示第 i 种水果的数量。(1<=ai<=106)
输出仅包含一个正整数,表示答案。
样例输入
5 1
45 39 90 65 15
样例输出
45
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.