题目描述

在一个遥远的星球上，这颗星球上的果树非常奇特，同一条直线上的果树只会长出不同种类的水果。

有一天小红乘飞船来到了这里，由于他的食物不多了，于是他决定在这颗星球上进行补给。他发现了一个 $n$ 棵果树长成的直线，其中第 $i$ 棵果树上有 $aᵢ$ 个第 $i$ 种水果。

小红想要品尝一部分这些独特的水果，现在小红可以对这个水果序列进行最多 $k$ 次操作，每次可选择一个连续的区间将其中的水果全部吃掉，但剩余的水果种类必须大于 $0$ 。

小红知道，这个星球上的水果都非常美味，每一种都有独特的口感和香味。小红不想错过任何一种美味的水果，所以小红希望在吃掉一些水果后，剩余水果中数量最少的那种尽可能多，以便在未来能够继续享用美味的水果。

现在问题来了：在上述情况下，剩余水果中数量最少的那种最多能有多少呢？

输入描述

输入第一行为两个正整数 $n$ 和 $k$ ，分别表示果树的数量以及最多的操作次数。($1<=n<=10^5$ ，$0<=k<=10^5$)

输入第二行为 $n$ 个正整数，其中第 $i$ 个数为 $aᵢ$ ，表示第 $i$ 种水果的数量。($1<=aᵢ<=10^6$)

输出描述

输出仅包含一个正整数，表示答案。

样例

样例输入

5 1
45 39 90 65 15

样例输出

45