最大 MEX

题目描述

给定一个长度为 $N$ 的非负整数序列 $A$。

从 $A$ 中选取 $K$ 个元素,并按原顺序拼接得到序列 $B$ 时,求 $MEX(B)$ 的最大可能值。

这里,对于序列 $X$,定义 $MEX(X)$ 为满足以下条件的唯一非负整数 $m$:

• 所有满足 $0 \le i \lt m$ 的整数 $i$ 都包含在 $X$ 中;
• $m$ 不包含在 $X$ 中。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案。

样例

7 3
2 0 2 3 2 1 9

3

在本输入中,$A=(2,0,2,3,2,1,9)$,需要从中选取 $K=3$ 个元素得到序列 $B$。例如:

• 选取第 $1$、$2$、$3$ 个元素时,$MEX(B)=MEX(2,0,2)=1$。
• 选取第 $3$、$4$、$6$ 个元素时,$MEX(B)=MEX(2,3,1)=0$。
• 选取第 $2$、$6$、$7$ 个元素时,$MEX(B)=MEX(0,1,9)=2$。
• 选取第 $2$、$3$、$6$ 个元素时,$MEX(B)=MEX(0,2,1)=3$。

$MEX$ 的最大可能值为 $3$。

数据范围

• 输入中的所有值均为整数。
• $1 \le K \le N \le 3 \times 10^5$
• $0 \le A_i \le 10^9$