当前没有测试数据。

C - 最大MEX

得分：300分

题目描述

给定一个长度为$N$的非负整数序列$A$，当$B$是从$A$中选取$K$个元素后按原顺序拼接而成的序列时，请找出$MEX(B)$的最大可能值。

这里，对于序列$X$，我们定义$MEX(X)$是满足以下条件的唯一非负整数$m$：

• 每个整数$i$满足$0 \le i < m$均在$X$中出现。
• $m$不在$X$中出现。

限制条件

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

输入

输入以以下格式从标准输入中给出：

$N$ $K$

$A_1$ $A_2$ $\dots$ $A_N$

输出

输出答案。

示例

输入1

7 3
2 0 2 3 2 1 9

输出1

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$。