MEXanization
Contest: CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3300
Tags: data structures

Let's define $$$f(S)$$$. Let $$$S$$$ be a multiset (i.e., it can contain repeated elements) of non-negative integers. In one operation, you can choose any non-empty subset of $$$S$$$ (which can also contain repeated elements), remove this subset (all elements in it) from $$$S$$$, and add the MEX of the removed subset to $$$S$$$. You can perform any number of such operations. After all the operations, $$$S$$$ should contain exactly $$$1$$$ number. $$$f(S)$$$ is the largest number that could remain in $$$S$$$ after any sequence of operations.

You are given an array of non-negative integers $$$a$$$ of length $$$n$$$. For each of its $$$n$$$ prefixes, calculate $$$f(S)$$$ if $$$S$$$ is the corresponding prefix (for the $$$i$$$-th prefix, $$$S$$$ consists of the first $$$i$$$ elements of array $$$a$$$).

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

- The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
- The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
- The MEX of $$$[0,3,1,2]$$$ is $$$4$$$, because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ belong to the array, but $$$4$$$ does not.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the size of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2 \cdot 10^5$$$) — the array $$$a$$$.

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

Output format:
For each test case, output $$$n$$$ numbers: $$$f(S)$$$ for each of the $$$n$$$ prefixes of array $$$a$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
Consider the first test case. For a prefix of length $$$1$$$, the initial multiset is $$$\{179\}$$$. If we do nothing, we get $$$179$$$.

For a prefix of length $$$2$$$, the initial multiset is $$$\{57, 179\}$$$. Using the following sequence of operations, we can obtain $$$2$$$.

1. Apply the operation to $$$\{57\}$$$, the multiset becomes $$$\{0, 179\}$$$.
2. Apply the operation to $$$\{179\}$$$, the multiset becomes $$$\{0, 0\}$$$.
3. Apply the operation to $$$\{0\}$$$, the multiset becomes $$$\{0, 1\}$$$.
4. Apply the operation to $$$\{0, 1\}$$$, the multiset becomes $$$\{2\}$$$. This is our answer.

Consider the second test case. For a prefix of length $$$1$$$, the initial multiset is $$$\{0\}$$$. If we apply the operation to $$$\{0\}$$$, the multiset becomes $$$\{1\}$$$. This is the answer.

Example input:
4
8
179 57 2 0 2 3 2 3
1
0
3
1 0 3
8
1 0 1 2 4 3 0 2

Example output:
179 2 3 3 3 4 4 5 
1 
1 2 2 
1 2 2 3 3 5 5 5

Editorial:
Let's start by introducing a more convenient way to store numbers - an array $$$cnt$$$, where $$$cnt[x]$$$ represents the number of occurrences of $$$x$$$ in the prefix for which we are finding the answer. All $$$x$$$ such that $$$x > n$$$ will be added to $$$cnt[0]$$$ because applying the operation to $$$\{x\}$$$ in such cases is optimal.
Let's introduce a few array operations that will be sufficient to solve the problem.
• Create the number $$$x$$$. Apply the operation to the set of numbers $$$\{0, 1, 2, \dots, x-1\}$$$. In terms of the array $$$cnt$$$, this is equivalent to subtracting $$$1$$$ from the range $$$0$$$ to $$$x-1$$$ and adding $$$1$$$ to $$$cnt[x]$$$.
• Turn the number $$$x$$$ into $$$0$$$. To do this, apply the operation to $$$\{x\}$$$. In terms of the array $$$cnt$$$, this is equivalent to subtracting $$$1$$$ from $$$cnt[x]$$$ and adding $$$1$$$ to $$$cnt[0]$$$.
• Create the number $$$x$$$ and clear the multiset. This is the same as creating the number $$$x$$$, but we apply the operation to all other numbers, leaving only the single number $$$x$$$ (or a larger number) in the set.
It can be proven that by using only operations of this kind, we can always obtain the optimal answer.
Now we can forget about the original condition and solve the problem for the array.
Let's learn how to check if it is possible to create the number $$$k$$$ and clear the multiset:
First, let's try to create the number $$$k$$$. If it is possible, the answer is yes. Otherwise, we look at the rightmost number that is missing (or in other words, the rightmost $$$0$$$). We try to create it, and now we need to find the rightmost element $$$\leq 1$$$ to the left of it, and so on. To implement this, we need to maintain a number $$$p$$$ such that we subtract $$$p$$$ from all elements in the prefix (initially $$$p=1$$$), iterate through the array from right to left, and if $$$cnt[i]<p$$$, assign $$$p \mathrel{{+}{=}} (p-cnt[i])$$$. When we reach zero, $$$p$$$ may be greater than $$$cnt[0]$$$, in which case we need to use the operation to turn any number into $$$0$$$. To do this, simply check that the remaining number of elements in the array is greater than or equal to $$$p$$$.
This currently works in $$$O(k)$$$ time, which is not very efficient.
Optimization techniques:
First, let's maintain the sum of elements $$$sm$$$ and as soon as it becomes negative, terminate the process. To achieve this, when subtracting $$$p-cnt[i]$$$ from $$$p$$$, let's subtract $$$(p-cnt[i])\cdot(i-1)$$$ from $$$sm$$$. Now let's use a bottom-up segment tree to find the nearest number smaller than $$$p$$$ to the left in $$$O(\log(i))$$$ time.
Now let's notice that when we update through $$$cnt[i]$$$, we subtract at least $$$i-1$$$ from $$$sm$$$, so there can't be more than $$$O(\sqrt(n))$$$ different values of $$$i$$$ through which we will update.
Now we can answer for a specific $$$k$$$ in $$$O(\sqrt(n) \cdot \log(n))$$$ time, but in reality, the complexity is $$$O(\sqrt(n))$$$ (due to the peculiarities of the bottom-up segment tree), and the authors have a proof for this, but they are afraid that you will find an error in it, so they decided not to provide it.
Now let's see how to solve the full problem:
Initially, the answer is $$$0$$$, and we notice that it does not decrease. So after each addition, we will check if it is possible to increase the answer and increase it as long as possible. The answer cannot exceed $$$n$$$, so we will perform no more than $$$2 \cdot n$$$ checks.
Overall, the solution works in $$$O(n \cdot \sqrt(n))$$$ time. That's how it is.