我的思路如下：

先二分第一问答案。

check 可以通过将 $A_i$ 分成大于等于 $mid$ 的和小于 $mid$ 的两类。

对于每一个极长的 $A_i$ 小于 $mid$ 的子段，设子段左端点为 $i$，右端点为 $j$，那么可以贪心地合并，求出合并次数。将所有子段的次数合起来，与 $N-K$ 比较。

贪心的正确性可以感性理解，如果 $A_i$ 与 $A_{i - 1}$ 合并，那么子段左边仍然是一个大于等于 $mid$ 的值，而 $A_{i+1}$ 的值没有改变。

如果将 $A_i$ 与 $A_{i+1}$ 合并，新的值则会更大，显然不会比前一种方法更劣。

得到第一问的解之后，通过倍增得出第二问的解。

我认为该方法的时间复杂度为 $\Omicron(n\log (nV))$ 的。

目前的问题是，在所有 $A_i$ 都小于 $mid$ 时，无法知道从哪个位置进行贪心。

求解答。