AtCoder Beginner Contest 194
翻译中…
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.
翻译中…
样例
Input #1
3 2
0 0 1
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$.
Input #2
3 2
1 1 1
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$
Input #3
3 2
0 1 0
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$
Input #4
7 3
0 0 1 2 0 1 0
Output #4
2
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。