CF1294D MEX maximizing

回忆一下，数组的 MEX（Minimum Excluded Number）是指不在数组中的最小非负整数。例如： - 对于数组 $[0, 0, 1, 0, 2]$，MEX 等于 $3$，因为 $0, 1, 2$ 都在数组中，而 $3$ 是最小的不在数组中的非负整数。 - 对于数组 $[1, 2, 3, 4]$，MEX 等于 $0$，因为 $0$ 是最小的不在数组中的非负整数。 - 对于数组 $[0, 1, 4, 3]$，MEX 等于 $2$，因为 $2$ 是最小的不在数组中的非负整数。 现在给定一个空数组 $a=[]$（即长度为零的数组），以及一个正整数 $x$。 接下来有 $q$ 个操作。第 $j$ 个操作给出一个整数 $y_j$，表示你需要将 $y_j$ 添加到数组末尾。每次操作后，数组长度增加 $1$。 你可以进行如下操作任意多次：选择任意一个下标 $i$，将 $a_i := a_i + x$ 或 $a_i := a_i - x$（即将数组中的任意一个元素增加或减少 $x$）。唯一的限制是 $a_i$ 不能变成负数。由于数组初始为空，只有在第一次操作后才能进行这些操作。 你的目标是：在每次操作后，经过任意多次上述操作（可以对同一个元素多次操作），使得数组的 MEX 尽可能大。你需要在每次操作后输出当前数组的最大 MEX。 注意，每次操作之间，所有对数组的操作都会被重置。也就是说，第 $j$ 次操作后，数组 $a$ 等于 $[y_1, y_2, \dots, y_j]$。

输入的第一行包含两个整数 $q, x$（$1 \leq q, x \leq 4 \times 10^5$），分别表示操作次数和 $x$ 的值。 接下来的 $q$ 行，每行一个整数 $y_j$（$0 \leq y_j \leq 10^9$），表示第 $j$ 次操作需要添加到数组的元素。

对于每次操作，输出当前数组的最大 MEX。也就是说，第 $j$ 行输出前 $j$ 次操作后数组的最大 MEX。注意，操作之间是相关的（数组会变化），但对数组元素的加减 $x$ 操作在每次操作之间是独立的。

以第一个样例为例： - 第一次操作后，数组为 $a=[0]$：无需进行任何操作，最大 MEX 为 $1$。 - 第二次操作后，数组为 $a=[0, 1]$：无需进行任何操作，最大 MEX 为 $2$。 - 第三次操作后，数组为 $a=[0, 1, 2]$：无需进行任何操作，最大 MEX 为 $3$。 - 第四次操作后，数组为 $a=[0, 1, 2, 2]$：无需进行任何操作，最大 MEX 为 $3$（无法通过操作使其更大）。 - 第五次操作后，数组为 $a=[0, 1, 2, 2, 0]$：可以进行 $a[4] := a[4] + 3 = 3$，数组变为 $a=[0, 1, 2, 2, 3]$，此时最大 MEX 为 $4$。 - 第六次操作后，数组为 $a=[0, 1, 2, 2, 0, 0]$：可以进行 $a[4] := a[4] + 3 = 3$，数组变为 $a=[0, 1, 2, 2, 3, 0]$，此时最大 MEX 为 $4$。 - 第七次操作后，数组为 $a=[0, 1, 2, 2, 0, 0, 10]$。可以进行如下操作： - $a[3] := a[3] + 3 = 2 + 3 = 5$， - $a[4] := a[4] + 3 = 0 + 3 = 3$， - $a[5] := a[5] + 3 = 0 + 3 = 3$， - $a[5] := a[5] + 3 = 3 + 3 = 6$， - $a[6] := a[6] - 3 = 10 - 3 = 7$， - $a[6] := a[6] - 3 = 7 - 3 = 4$。 最终数组变为 $a=[0, 1, 2, 5, 3, 6, 4]$，此时最大 MEX 为 $7$。 由 ChatGPT 4.1 翻译