← 返回题目列表

Codeforces · 2226/E

E. 精神纪念碑(硬版)

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

这是这个问题的困难版本。在此版本中,您需要查找 $$$a$$$ 的每个前缀的 $$$f(\cdot)$$$ 的值。

对于任何数组 $$$[c_1, c_2, \ldots, c_m]$$$,我们将 $$$f(c)$$$ 定义为 最大 可能的 $$$\operatorname{mex}(c)$$$$$$^{\text{*}}$$$ 可以通过执行以下操作一次来实现:

  • 选择一个整数数组$$$[b_1, b_2, \ldots, b_m]$$$,使得$$$b_i \ge 1$$$对于所有$$$1 \le i \le m$$$;
  • 为每个 $$$1 \le i \le m$$$ 设置 $$$c_i := c_i \, \bmod \, b_i$$$$$$^{\text{†}}$$$。

给定一个数组 $$$a$$$,其中包含 $$$n$$$ 非负整数。对于每个前缀 $$$a^{(i)} = [a_1, a_2, \ldots, a_i]$$$,确定 $$$f(a^{(i)})$$$ 的值。

$$$^{\text{*}}$$$$$$\operatorname{mex}(c)$$$ 表示 $$$c$$$ 中整数的最小排除数 (MEX)。例如,$$$\operatorname{mex}([2,2,1])=0$$$,因为$$$0$$$不属于数组,$$$\operatorname{mex}([0,3,1,2])=4$$$,因为$$$0$$$、$$$1$$$、$$$2$$$和$$$3$$$出现在数组中,但$$$4$$$出现在数组中没有。

$$$^{\text{†}}$$$$$$u \bmod v$$$ 表示 $$$u$$$ 除以 $$$v$$$ 所得的余数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。保证所有测试用例的$$$\max(a_1,a_2,\ldots,a_n)$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出 $$$n$$$ 个整数 - 其中第 $$$i$$$ 个整数表示 $$$f([a_1, a_2, \ldots, a_i])$$$ 的值。

示例

输入
复制

4
4
0 1 2 3
2
6 7
6
8 1 7 6 4 3
9
9 9 8 2 4 4 3 5 3

输出
复制

1 2 3 4
1 2
1 2 3 4 5 5
1 2 3 4 5 5 5 6 6

注意

考虑第一个测试用例,

  • $$$a^{(1)} = [0]$$$,选择 $$$b = [1]$$$ 给出 $$$\operatorname{mex} = 1$$$。
  • $$$a^{(2)} = [0, 1]$$$,选择 $$$b = [1, 2]$$$ 给出 $$$\operatorname{mex} = 2$$$。
  • $$$a^{(3)} = [0, 1, 2]$$$,选择 $$$b = [1, 2, 3]$$$ 给出 $$$\operatorname{mex} = 3$$$。
  • $$$a^{(4)} = [0, 1, 2, 3]$$$,选择 $$$b = [1, 2, 3, 4]$$$ 给出 $$$\operatorname{mex} = 4$$$。

考虑第二个测试用例,

  • $$$a^{(1)} = [6]$$$,选择 $$$b = [6]$$$ 给出 $$$\operatorname{mex} = 1$$$。
  • $$$a^{(2)} = [6, 7]$$$,选择 $$$b = [3, 3]$$$ 给出 $$$\operatorname{mex} = 2$$$。