CF2226E.Mental Monumental (Hard Version)

This is the hard version of this problem. In this version, you are required to find the values of $f(\cdot)$ for each prefix of $a$.

For any array $[c_1, c_2, \ldots, c_m]$, we define $f(c)$ as the maximum possible $\operatorname{mex}(c)$$^{\text{∗}}$ that can be achieved by performing the following operation exactly once:

• Choose an integer array $[b_1, b_2, \ldots, b_m]$ such that $b_i \ge 1$ for all $1 \le i \le m$;
• Set $c_i := c_i \, \bmod \, b_i$$^{\text{†}}$ for every $1 \le i \le m$.

You are given an array $a$ consisting of $n$ non-negative integers. For each prefix $a^{(i)} = [a_1, a_2, \ldots, a_i]$, determine the value of $f(a^{(i)})$.

$^{\text{∗}}$$\operatorname{mex}(c)$ denotes the minimum excluded (MEX) of the integers in $c$. For example, $\operatorname{mex}([2,2,1])=0$ because $0$ does not belong to the array, and $\operatorname{mex}([0,3,1,2])=4$ because $0$, $1$, $2$, and $3$ appear in the array, but $4$ does not.

$^{\text{†}}$$u \bmod v$ denotes the remainder from dividing $u$ by $v$.

这是本题的困难版本。在本版本中，你需要对数组 $a$ 的每个前缀分别求出 $f(\cdot)$ 的值。

对于任意数组 $[c_1, c_2, \ldots, c_m]$，我们定义 $f(c)$ 为：在恰好执行一次如下操作的前提下，所能达到的最大可能的 $\operatorname{mex}(c)$$^{\text{∗}}$ 值：

• 选择一个整数数组 $[b_1, b_2, \ldots, b_m]$，满足对所有 $1 \le i \le m$ 均有 $b_i \ge 1$；
• 对每个 $1 \le i \le 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$ 所得的余数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. It is guaranteed that the sum of $\max(a_1,a_2,\ldots,a_n)$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each testcase, output $n$ integers — where the $i$-th integer represents the value of $f([a_1, a_2, \ldots, a_i])$.

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

Consider the first testcase,

• $a^{(1)} = [0]$, choosing $b = [1]$ gives $\operatorname{mex} = 1$.
• $a^{(2)} = [0, 1]$, choosing $b = [1, 2]$ gives $\operatorname{mex} = 2$.
• $a^{(3)} = [0, 1, 2]$, choosing $b = [1, 2, 3]$ gives $\operatorname{mex} = 3$.
• $a^{(4)} = [0, 1, 2, 3]$, choosing $b = [1, 2, 3, 4]$ gives $\operatorname{mex} = 4$.

Consider the second testcase,

• $a^{(1)} = [6]$, choosing $b = [6]$ gives $\operatorname{mex} = 1$.
• $a^{(2)} = [6, 7]$, choosing $b = [3, 3]$ gives $\operatorname{mex} = 2$.

考虑第一个测试用例：

• $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$。