删数游戏(delete)

题目描述

长度为$n$的序列$A$，从中删去恰好$k$个元素（右边的元素往左边移动），记$cnt$为新序列中$A_{i}=i$的元素个数（即权值与下标相同的元素的个数）。求$cnt$的最大值。

输入格式

第一行两个正整数$n$，$k$，分别表示序列长度，删去元素的个数。

第二行$n$个正整数$A_{1}..A_{n}$，描述序列$A$。

输出格式

一行一个整数，表示$cnt$的最大值。

样例

input1

8 3
1 1 3 2 4 5 7 5

output1

4

explanation

删掉序列中的第$4$,$7$,$8$个数。

input2

见ex_delete2.in。

output2

见ex_delete2.out。

数据范围和约定

对于$20\%$的数据，$n\le20$。

对于$40\%$的数据，$n\le500$。

对于$60\%$的数据，$n\le5000$。

对于$80\%$的数据，$n\le100000$。

对于$100\%$的数据，$n\le1000000$,$A_{i}\le 10^9$,$k\le n$。

时间限制：$1s$ 空间限制：$512MB$

样例下载

样例下载