Max MEX

题目描述

你被给定一个长度为 $N$ 的非负整数序列。
当序列 $B$ 是通过从 $A$ 中选择 $K$ 个元素并在不改变相对顺序的情况下将它们连接而得到时，求 $MEX(B)$ 的最大可能值。 这里，对于序列 $X$，我们将 $MEX(X)$ 定义为满足下列条件的唯一非负整数 $m$：

对于所有满足 0 \le i < m 的整数 $i$，$i$ 都出现在 $X$ 中。 $m$ 不出现在 $X$ 中。

输入格式

输入按下列格式由标准输入给出： $N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案。

7 3
2 0 2 3 2 1 9

3

提示

输入中的所有数值均为整数。 $1 \le K \le N \le 3 \times 10^5$ $0 \le A_i \le 10^9$在此输入中，$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$.

标签: AtCoder|abc290C

来源

AtCoder|abc290C