E. Ещё одна задача про MEX
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим вес массива $$$b$$$, состоящего из $$$m$$$ целых неотрицательных чисел, как количество индексов $$$i$$$ ($$$1\le i\le m$$$), удовлетворяющих условию $$$b_i \gt \operatorname{mex}(b)$$$. Здесь $$$\operatorname{mex}(b)$$$ обозначает наименьшее исключенное (MEX)$$$^{\text{∗}}$$$ целое число в массиве $$$b$$$.

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых неотрицательных чисел. Для его подмассива$$$^{\text{†}}$$$ $$$[a_l, a_{l+1}, \ldots, a_r]$$$ обозначим вес подмассива как $$$w(l,r)$$$.

Для каждого $$$1\le i\le n$$$ вам нужно найти максимальный вес среди всех подмассивов массива $$$a$$$, заканчивающихся на индексе $$$i$$$. Другими словами, вам нужно найти $$$\max\limits_{1\le l\le i} w(l, i)$$$ для каждого $$$1\le i\le n$$$.

$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$b_1, b_2, \ldots, b_m$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$b$$$.

$$$^{\text{†}}$$$Массив $$$c$$$ является подмассивом массива $$$a$$$, если $$$c$$$ может быть получен из $$$a$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n \le 3\cdot 10^5$$$) — длину массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le n$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел, где $$$i$$$-е целое число обозначает максимальный вес среди всех подмассивов массива $$$a$$$, заканчивающихся на индексе $$$i$$$, т.е. $$$\max\limits_{1\le l\le i}w(l,i)$$$.

Пример
Входные данные
6
1
0
5
2 0 3 0 1
6
0 1 2 3 5 4
7
0 2 2 0 4 1 3
8
2 1 0 3 0 2 1 3
15
0 1 9 1 0 2 5 3 7 0 4 15 2 0 1
Выходные данные
0 
1 1 2 2 1 
0 1 2 3 4 5 
0 1 2 2 3 2 3 
1 2 0 1 1 2 2 3 
0 1 2 3 1 1 2 3 4 4 5 6 7 7 3
Примечание

В первом наборе входных данных мы имеем $$$w(1, 1) = 0$$$, потому что $$$\operatorname{mex}([a_1]) = 1$$$, и нет индексов, удовлетворяющих условию $$$a_i \gt 1$$$.

Во втором наборе входных данных мы можем вычислить вес каждого подмассива массива $$$[l,r]$$$ по определению:

  1. $$$w(1,1)=1$$$. Таким образом, $$$\max\limits_{1\le l\le 1}w(l,1) =1$$$;
  2. $$$w(1,2)=1$$$ и $$$w(2,2)=0$$$. Таким образом, $$$\max\limits_{1\le l\le 2}w(l,2) =1$$$;
  3. $$$w(1,3)=2$$$ и $$$w(2,3)=w(3,3)=1$$$. Таким образом, $$$\max\limits_{1\le l\le 3}w(l,3) =2$$$;
  4. $$$w(1,4)=2$$$, $$$w(2,4)=w(3,4)=1$$$, и $$$w(4,4)=0$$$. Таким образом, $$$\max\limits_{1\le l\le 4}w(l,4) =2$$$;
  5. $$$w(1,5)=0$$$, $$$w(2,5)=w(3,5)=1$$$, и $$$w(4,5)=0,w(5,5)=1$$$. Таким образом, $$$\max\limits_{1\le l\le 5}w(l,5) =1$$$.

Например, $$$w(1, 4) = 2$$$, потому что $$$\operatorname{mex}([a_1, a_2, a_3, a_4]) = 1$$$, и в подмассиве есть два индекса, удовлетворяющих условию $$$a_i \gt 1$$$: $$$1$$$ и $$$3$$$.