← 返回题目列表

AtCoder · abc290_c

E. 最大 MEX

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个长度-N 非负整数序列。
当 B 是通过选择获得的序列 K 元素来自 A 并将它们连接起来而不改变顺序,找到最大可能值 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),您将获得序列 B 通过采摘 K=3 元素。 例如,

  • 如果 1-st, 2-nd,和 3-rd 元素被选择, MEX(B)=MEX(2,0,2)=1.
  • 如果 3-rd, 选择 4-th,以及 6第一个元素, MEX(B)=MEX(2,3,1)=0.
  • 如果 2-nd, 6-th,以及 7第一个元素, MEX(B)=MEX(0,1,9)=2.
  • 如果 2-nd, 3-rd,和 6第一个元素, MEX(B)=MEX(0,2,1)=3.

最大可能 MEX is 3.