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 $ .

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] $ , 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 $ .