CF2146E.Yet Another MEX Problem

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.

我们定义一个由 $m$ 个非负整数组成的数组 $b$ 的权重为满足 $b_i \gt \operatorname{mex}(b)$ 的下标 $i$（其中 $1\le i\le m$）的个数。这里，$\operatorname{mex}(b)$ 表示数组 $b$ 中元素的最小未出现值（MEX）$^{\text{∗}}$。

给定一个由 $n$ 个非负整数组成的数组 $a$。对于其子数组$^{\text{†}}$ $[a_l, a_{l+1}, \ldots, a_r]$，我们记该子数组的权重为 $w(l,r)$。

对每个 $1\le i\le n$，你需要找出所有以索引 $i$ 结尾的 $a$ 的子数组中权重的最大值。换言之，对每个 $1\le i\le n$，你需要计算 $\max\limits_{1\le l\le i} w(l, i)$。

$^{\text{∗}}$ 一组整数 $b_1, b_2, \ldots, b_m$ 的**最小未出现值（MEX）**定义为不在该集合 $b$ 中出现的最小非负整数 $x$。

$^{\text{†}}$ 若数组 $c$ 可通过从数组 $a$ 的开头删除若干（可能为零个或全部）元素、并从结尾删除若干（可能为零个或全部）元素而得到，则称 $c$ 是 $a$ 的一个子数组。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

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

对于每个测试用例，输出 $n$ 个整数，其中第 $i$ 个整数表示所有以索引 $i$ 结尾的子数组 $a$ 的最大权重，即 $\max\limits_{1\le l\le i}w(l,i)$。

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

在第一个测试用例中，我们有 $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$。