E - Mex Min

分数 : $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$ $\dots$ $A_N$

输出

输出结果。

3 2
0 0 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$。

3 2
1 1 1

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 2
0 1 0

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$

7 3
0 0 1 2 0 1 0

2