这是这个问题的困难版本。在此版本中,您需要查找 $$$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])$$$ 的值。
示例
输入复制
440 1 2 326 768 1 7 6 4 399 9 8 2 4 4 3 5 3
输出复制
1 2 3 41 21 2 3 4 5 51 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$$$。