E. Yet Another MEX Problem
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

We define the weight of an array $$$b$$$ consisting of $$$m$$$ non-negative integers as the number of indices $$$i$$$ ($$$1\le i\le m$$$) satisfying $$$b_i \gt \operatorname{mex}(b)$$$. Here, $$$\operatorname{mex}(b)$$$ denotes the minimum excluded (MEX)$$$^{\text{∗}}$$$ of the integers in $$$b$$$.

You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers. For its subarray$$$^{\text{†}}$$$ $$$[a_l, a_{l+1}, \ldots, a_r]$$$, we denote the weight of the subarray as $$$w(l,r)$$$.

For every $$$1\le i\le n$$$, you have to find the maximum weight over all subarrays of $$$a$$$ ending at index $$$i$$$. In other words, you have to find $$$\max\limits_{1\le l\le i} w(l, i)$$$ for every $$$1\le i\le n$$$.

$$$^{\text{∗}}$$$The minimum excluded (MEX) of a collection of integers $$$b_1, b_2, \ldots, b_m$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the collection $$$b$$$.

$$$^{\text{†}}$$$An array $$$c$$$ is a subarray of an array $$$a$$$ if $$$c$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

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 test case contains a single integer $$$n$$$ ($$$1\le n \le 3\cdot 10^5$$$) — the length of $$$a$$$.

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers, the $$$i$$$-th integer denoting the maximum weight over all subarrays of $$$a$$$ ending at index $$$i$$$, i.e., $$$\max\limits_{1\le l\le i}w(l,i)$$$.

Example
Input
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
Output
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
Note

In the first test case, we have $$$w(1, 1) = 0$$$, because $$$\operatorname{mex}([a_1]) = 1$$$, and there are no indices satisfying $$$a_i \gt 1$$$.

In the second test case, we can calculate the weight of each subarray $$$[l,r]$$$ by the definition:

  1. $$$w(1,1)=1$$$. Thus, $$$\max\limits_{1\le l\le 1}w(l,1) =1$$$;
  2. $$$w(1,2)=1$$$ and $$$w(2,2)=0$$$. Thus, $$$\max\limits_{1\le l\le 2}w(l,2) =1$$$;
  3. $$$w(1,3)=2$$$ and $$$w(2,3)=w(3,3)=1$$$. Thus, $$$\max\limits_{1\le l\le 3}w(l,3) =2$$$;
  4. $$$w(1,4)=2$$$, $$$w(2,4)=w(3,4)=1$$$, and $$$w(4,4)=0$$$. Thus, $$$\max\limits_{1\le l\le 4}w(l,4) =2$$$;
  5. $$$w(1,5)=0$$$, $$$w(2,5)=w(3,5)=1$$$, and $$$w(4,5)=0,w(5,5)=1$$$. Thus, $$$\max\limits_{1\le l\le 5}w(l,5) =1$$$.

For example, $$$w(1, 4) = 2$$$ because $$$\operatorname{mex}([a_1, a_2, a_3, a_4]) = 1$$$, and there are two indices satisfying $$$a_i \gt 1$$$ in the subarray: $$$1$$$ and $$$3$$$.