AT_abc194_e.[ABC194E] Mex Min

定义 $ \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 $ 个值中，求出最小值。

输入以以下格式从标准输入读入：

$ N $ $ M $ $ A_1 $ $ A_2 $ $ A_3 $ $ \cdots $ $ A_N $

输出答案。

限制条件

• $ 1 \le M \le N \le 1.5 \times 10^6 $
• $ 0 \le A_i < N $
• 输入中的所有值均为整数

样例解释 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 $，答案为 $ 1 $。

样例解释 2

• 当 $ 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 $
  因此答案为 $ 0 $。

样例解释 3

• 当 $ 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 $
  因此答案为 $ 2 $。

由 ChatGPT 4.1 翻译