UOJ Logo

NOI.AC

1S 512MB

#46. delete

统计

删数游戏(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$

样例下载

样例下载