/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の非負整数列 A が与えられます。
A から K 要素を選んで順序を保ったまま抜き出した列を B としたとき、 MEX(B) としてありえる最大値を求めてください。
但し、数列 X に対して MEX(X) は以下の条件を満たす唯一の非負整数 m として定義されます。
- 0 \le i < m を満たす全ての整数 i が 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 です。
Score : 300 points
Problem Statement
You are given a length-N sequence of non-negative integers.
When B is a sequence obtained by choosing K elements from A and concatenating them without changing the order, find the maximum possible value of MEX(B).
Here, for a sequence X, we define MEX(X) as the unique non-negative integer m that satisfies the following conditions:
- Every integer i such that 0 \le i < m is contained in X.
- m is not contained in X.
Constraints
- All values in the input are integers.
- 1 \le K \le N \le 3 \times 10^5
- 0 \le A_i \le 10^9
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
7 3 2 0 2 3 2 1 9
Sample Output 1
3
In this input, A=(2,0,2,3,2,1,9), and you obtain the sequence B by picking K=3 elements. For example,
- If the 1-st, 2-nd, and 3-rd elements are chosen, MEX(B)=MEX(2,0,2)=1.
- If the 3-rd, 4-th, and 6-th elements are chosen, MEX(B)=MEX(2,3,1)=0.
- If the 2-nd, 6-th, and 7-th elements are chosen, MEX(B)=MEX(0,1,9)=2.
- If the 2-nd, 3-rd, and 6-th elements are chosen, MEX(B)=MEX(0,2,1)=3.
The maximum possible MEX is 3.