E. Ментально монументально (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам требуется найти значения $$$f(\cdot)$$$ для каждого префикса $$$a$$$.

Для любого массива $$$[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$$$;
  • Присвоить $$$c_i := c_i \, \bmod \, b_i$$$$$$^{\text{†}}$$$ для каждого $$$1 \le i \le m$$$.

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых неотрицательных чисел. Для каждого префикса $$$a^{(i)} = [a_1, a_2, \ldots, a_i]$$$ определите значение $$$f(a^{(i)})$$$.

$$$^{\text{∗}}$$$$$$\operatorname{mex}(c)$$$ обозначает минимальное целое неотрицательное число, отсутствующее среди элементов массива $$$c$$$. Например, $$$\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])$$$.

Пример
Входные данные
4
4
0 1 2 3
2
6 7
6
8 1 7 6 4 3
9
9 9 8 2 4 4 3 5 3
Выходные данные
1 2 3 4
1 2
1 2 3 4 5 5
1 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$$$.