题目描述

作为制卡大师的兰奇，发明了一种自助型卡牌游戏。

给定 $n$ 张卡牌，第 $i$ 张卡牌编号为 $i$，其权值为 $a_i$，卡牌的权值互不相同。

这个卡牌游戏的规则需要自己生成。一开始，所有的牌都在备选区。从备选区中选取一张编号最小的卡牌放到手牌区，便可进入规则生成阶段。

规则生成阶段的步骤如下：

1. 将手牌区的任意一张牌弃置到废牌区之中。

2. 然后在备选区中选择一张编号和权值均大于当前弃牌的牌，加入手牌区。若存在这样的一张牌，则称这张牌与弃牌互为置换；若不存在这样的一张牌，则跳过当前步骤。

3. 继续从备选区中选择一张编号大于当前弃牌且权值小于当前弃牌的牌，加入手牌区。若存在这样的一张牌，则同样可称这张牌与弃牌互为置换；若不存在这样的一张牌，则跳过当前步骤。

4. 完成以上步骤后，若手牌区没有卡牌了，则规则生成阶段结束。若仍有卡牌，则继续重复上述步骤，直到手牌区没有卡牌。

为了保证生成置换的唯一性，兰奇规定规则生成阶段合法当且仅当规则生成结束后，所有的牌都在废牌区。并且在正式游戏阶段一张编号较大的牌经过一系列操作后得到一张编号较小的牌后，该编号较大的牌，均要满足能够有机会按照在手牌区出现过的该张编号较小的牌的弃牌后生成的置换相同的步骤在规则生成阶段成为编号较小的牌的置换；若手牌区未出现该张编号较小的牌的弃牌后生成的置换，则无需考虑。否则，生成的置换是无效的。

可以证明在规则生成阶段合法的情况下，每张卡牌可以与哪些卡牌互为置换的方案是唯一的。

正式游戏阶段的步骤如下：

1. 选择任意一张卡牌作为起始卡牌并加入手牌区，然后进入下一步骤。

2. 将前手牌区的卡牌弃入废牌堆，然后从备选区中选择一张该卡牌的置换加入手牌区。若当前弃置的卡牌在备选区没有置换，则正式游戏阶段结束；反之，则得分增加 $1$ 分，然后继续重复步骤 2。

游戏发售后，销量并不是很好。因为游戏规则太复杂了。玩家们希望删去一些卡牌，使得正式游戏阶段的最大得分不超过 $k$。

而兰奇为了保证游戏的不做太大的改动，他要求删去一些卡牌后，保留下来的任意一张卡牌重新生成的置换要与原来未删去卡牌情况下的置换相同。

删去后置换仍相同的定义是：设 $S$ 表示某一张卡牌，未删除任何一张卡牌时的置换集合；$T$ 表示该张卡牌，在删除了部分卡牌时的置换集合。此时，满足 $T \subseteq S$。则称删去部分卡牌后，该卡牌的置换与原来未删去卡牌情况下的置换相同。

兰奇想知道，在满足了玩家和自己的要求的前提下，他最少要删除几张卡片。

输入格式

第一行输入两个正整数 $n$ 和 $k$，分别表示卡牌的数量和正式游戏阶段的最大得分不能超过的值。

第二行输入 $n$ 个元素，第 $i$ 个元素 $a_i$，表示编号为 $i$ 的卡牌权值。

输出格式

输出一个正整数，表示在满足玩家和自己的要求的前提下，最少要删除几张卡片。

3 2
1 2 3

0

6 2
3 2 7 99 10 15

3

提示

【样例1解释】

编号为 $1$ 的卡牌与编号为 $2$ 的卡牌互为置换，编号为 $2$ 的卡牌与编号为 $3$ 的卡牌互为置换。

所以，在不删去的情况下，获得最大得分的方案是：用编号为 $1$ 的卡牌作为起始卡牌置换出编号为 $2$ 的卡牌，然后再置换出编号为 $3$ 的卡牌。该方案的最大得分为 $2$，所以不需要删除任何一张卡牌。

【数据范围】

本题采用捆绑测试。

• Subtask 1（15 points）：$n \le 10$。
• Subtask 2（5 points）：$k = n$。
• Subtask 3（80 points）：无特殊限制。

对于所有测试数据，$1 \le n \le 2000$，$1 \le a_i \le 10^9$。