← 返回题目列表

AtCoder · abc194_e

E. 墨西哥分钟

中文机器翻译题面 查看原题

分数: 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).
对于每个整数 i 这样 0 \le i \le N - M,我们计算 \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

输出

打印答案。


示例输入 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