CF2226E Mental Monumental (Hard Version)

这是该问题的难度较高版本。在本版本中，你需要对于数组 $a$ 的每一个前缀，求出 $f(\cdot)$ 的值。 对于任意数组 $[c_1, c_2, \ldots, c_m]$，我们定义 $f(c)$ 为通过以下操作恰好执行一次后能够获得的最大可能的 $\operatorname{mex}(c)^{\text{∗}}$： - 任选一个整数数组 $[b_1, b_2, \ldots, b_m]$，使得对所有 $1 \leq i \leq m$ 都有 $b_i \geq 1$； - 对每个 $1 \leq i \leq m$，令 $c_i := c_i \bmod b_i$ $^{\text{†}}$。 现给定一个由 $n$ 个非负整数组成的数组 $a$。对于每个前缀 $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 \leq t \leq 10^4$）。接下来是每组测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 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])$ 的值。

考虑第一个测试用例， - $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$。 由 ChatGPT 5 翻译