/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
\mathrm{mex}(x_1, x_2, x_3, \dots, x_k) を、x_1, x_2, x_3, \dots, x_k に含まれない最小の非負整数と定義します。
長さ N の整数列 A = (A_1, A_2, A_3, \dots, A_N) が与えられます。
0 \le i \le N - M を満たす全ての整数 i について \mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M}) を計算したとき、この N - M + 1 個の値のうちの最小値を求めてください。
制約
- 1 \le M \le N \le 1.5 \times 10^6
- 0 \le A_i \lt N
- 入力に含まれる値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 A_3 \cdots A_N
出力
答えを出力せよ。
入力例 1
3 2 0 0 1
出力例 1
1
- i = 0 のとき : \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(0, 0) = 1
- i = 1 のとき : \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(0, 1) = 2
よって 1 と 2 のうちの最小値である 1 が答えです。
入力例 2
3 2 1 1 1
出力例 2
0
- i = 0 のとき : \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(1, 1) = 0
- i = 1 のとき : \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(1, 1) = 0
となります。
入力例 3
3 2 0 1 0
出力例 3
2
- i = 0 のとき : \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(0, 1) = 2
- i = 1 のとき : \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(1, 0) = 2
となります。
入力例 4
7 3 0 0 1 2 0 1 0
出力例 4
2
Score : 500 points
Problem Statement
Let us define \mathrm{mex}(x_1, x_2, x_3, \dots, x_k) as the smallest non-negative integer that does not occur in x_1, x_2, x_3, \dots, x_k.
You are given an integer sequence of length N: A = (A_1, A_2, A_3, \dots, A_N).
For each integer i such that 0 \le i \le N - M, we compute \mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M}). Find the minimum among the results of these N - M + 1 computations.
Constraints
- 1 \le M \le N \le 1.5 \times 10^6
- 0 \le A_i \lt N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 A_3 \dots A_N
Output
Print the answer.
Sample Input 1
3 2 0 0 1
Sample Output 1
1
We have:
- for i = 0: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(0, 0) = 1
- for i = 1: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(0, 1) = 2
Thus, the answer is the minimum among 1 and 2, which is 1.
Sample Input 2
3 2 1 1 1
Sample Output 2
0
We have:
- for i = 0: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(1, 1) = 0
- for i = 1: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(1, 1) = 0
Sample Input 3
3 2 0 1 0
Sample Output 3
2
We have:
- for i = 0: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(0, 1) = 2
- for i = 1: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(1, 0) = 2
Sample Input 4
7 3 0 0 1 2 0 1 0
Sample Output 4
2