P15340 [GCPC 2025] Mex Hex

家乡的宁静被附近一只魔法山猫响亮呼噜声和夜间潜行打破了。市长派你去吓跑它——毕竟，你是城市的个人财产及其他灾难守护者。你接受了挑战，准备去吓跑这只雄伟的动物。 为了保护自己，魔法山猫（顾名思义）试图用非常规的方式伤害你。它攻击时，会施放若干魔法咒语。每个咒语都以特定的 *势能* 施放，势能可以用一个自然数¹ 表示。如果你被势能为 $p_1, p_2, \dots, p_n$ 的咒语击中，那么你将感受到的疼痛值为 $\mathrm{mex}(\{p_1, p_2, \dots, p_n\})$，其中 $\mathrm{mex}$ 表示最小排除值²。注意，咒语不会立即造成伤害。只有在所有咒语施放完毕后，你才会根据它们势能的 $\mathrm{mex}$ 感受到疼痛。 为了保护自己，你带了一个 *护盾*，它也可以通过魔法偏转咒语。你的护盾有一个 *激活持续时间* $d$，这意味着当你激活护盾时，接下来的 $d$ 个咒语不会击中你。之后，护盾必须重新充能魔法，并且在接下来的 $d$ 个咒语期间无法再次激活。除此之外，你可以任意多次激活护盾。为了确保你能好好吓唬魔法山猫，市长要求你悄悄接近它。由于山猫会发现你激活魔法护盾时的光芒，你最早只能在站到这个罪魁祸首面前时，也就是在它施放第一个咒语之前，才能激活护盾。 :::align{center}  图 M.1：样例 3 的图示。方框中的数字表示咒语的势能。在此例中，你的护盾激活持续时间为 $d = 2$。通过在第 5、第 9 和第 14 个咒语之前激活护盾，你阻挡了绿色下划线的咒语。对于红色虚线划线的咒语，你无法激活护盾，因为在这些时间点护盾正在重新充能。 ::: 你现在必须制定一个策略，以承受尽可能小的疼痛。通过研究之前与魔法山猫的遭遇，你知道将要施放给你的咒语的势能。如果你最优地激活护盾，你能从中获得的最小疼痛值是多少？ ¹ 为此任务的目的，自然数定义为 $\mathbb{N} = \{0, 1, 2, \dots\}$。 ² 给定一个集合 $S \subseteq \mathbb{N}$，$S \neq \mathbb{N}$，$\mathrm{mex}(S)$ 是 *不包含* 在 $S$ 中的最小自然数 $m \in \mathbb{N}$。

输入包含： - 一行两个整数 $n$ 和 $d$（$1 \leq n \leq 10^5$，$1 \leq d \leq n$），表示咒语的数量和护盾的激活持续时间。 - 一行 $n$ 个整数 $p_1, \dots, p_n$（$0 \leq p_i < n$），表示 $n$ 个咒语的势能。

输出一个整数，表示你能从咒语中获得的最小疼痛值。

#### 样例 1 解释 你可以为第一个咒语激活护盾，让它为第二个咒语重新充能，为第三个咒语再次激活，为第四个重新充能，并在第五个咒语再次激活。这意味着只有两个势能为 $1$ 的咒语击中了你。由于 $\mathrm{mex}(\{1, 1\}) = 0$，你承受的疼痛为 $0$。 #### 样例 2 解释 无论你如何激活护盾，在它重新充能期间，总有一个势能为 $0$ 的咒语和一个势能为 $1$ 的咒语击中你。因此，击中你的咒语的 $\mathrm{mex}$ 至少为 $2$。完全不使用护盾即可达到此疼痛值。 #### 样例 3 解释 按照图 M.1 所示使用护盾。那么击中你的咒语势能为 $8, 1, 1, 0, 0, 1, 0, 6$ 和 $4$。这些势能的 $\mathrm{mex}$ 为 $2$。可以证明，没有任何激活护盾的方式能使剩余咒语势能的 $\mathrm{mex}$ 为 $0$ 或 $1$。 #### 样例 4 解释 回想一下，你最早只能在第一个咒语之前激活护盾。因此，你无法阻挡两个势能为 $0$ 的咒语。相反，通过阻挡第二个和第三个咒语，所有击中你的咒语势能均为 $0$。 翻译由 DeepSeek 完成