[SCOI2014] 方氏玉米田 (LIS + 二维BIT)

[SCOI2014] 方伯伯的玉米田

题目描述

方伯伯漫步在他的农田边缘时突然发现田中一排玉米显得十分杂乱。这些植株共计有 N 株其高度各不相同。为了达到视觉上的最佳效果方伯伯倾向于让植物呈现出一种有序排列的趋势因此他决定通过连续提升的方式对这些植株进行调整最终目标是使剩余植株的高度呈现出一种严格的递增趋势即形成单调递增序列这一过程需要满足一定的条件即每次提升操作只能作用于选中的连续区间并且每次操作只能提升所有选中植株的高度一次而整体的操作次数不能超过给定限制 K 。除此之外为了进一步优化视觉效果他还允许移除任何一组植株都可以自由决定数量和位置从而在保证整体美观的前提下最大化地保留剩余的数量这一策略不仅能够显著提高观赏体验还能有效减少资源浪费是一个非常值得探索的方向

输入格式

本段的第一行给出了两个整数n,K；它们分别代表了这一排玉米的总数目以及最多可执行的操作次数。接下来的一行则包含了n个整数a_1,a_2,\dots,a_n；其中a_i代表从左往右第i株玉米的高度。

输出格式

输出一个整数，最多剩下的玉米数。

样例 #1

样例输入 #1

    3 1
    2 1 3

样例输出 #1

    3

提示

100\% 的