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). 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). For each testcase, output (n) integers — where the (i)-th integer represents the value of (f(a_1, a_2, \ldots, a_i)). Consider the first testcase, (a^{(1)} = 0), choosin