White Magic
Contest: Codeforces Round 1004 (Div. 1)
Difficulty rating: 1900
Tags: constructive algorithms, data structures, dp, greedy, implementation

We call a sequence $$$a_1, a_2, \ldots, a_n$$$ magical if for all $$$1 \leq i \leq n-1$$$ it holds that: $$$\operatorname{min}(a_1, \ldots, a_i) \geq \operatorname{mex}(a_{i+1}, \ldots, a_n)$$$. In particular, any sequence of length $$$1$$$ is considered magical.

The minimum excluded (MEX) of a collection of integers $$$a_1, a_2, \ldots, a_k$$$ is defined as the smallest non-negative integer $$$t$$$ which does not occur in the collection $$$a$$$.

You are given a sequence $$$a$$$ of $$$n$$$ non-negative integers. Find the maximum possible length of a magical subsequence$$$^{\text{∗}}$$$ of the sequence $$$a$$$.

Input format:
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 an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the sequence $$$a$$$.

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

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

Output format:
For each test case, output a single number — the maximum possible length of a magical subsequence of the sequence $$$a$$$.

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

Note:
In the first test case, the sequence $$$[4, 3, 2, 1, 0]$$$ is magical, since:

- $$$\operatorname{min}(4) = 4, \operatorname{mex}(3, 2, 1, 0) = 4$$$. $$$4 \geq 4$$$
- $$$\operatorname{min}(4, 3) = 3, \operatorname{mex}(2, 1, 0) = 3$$$. $$$3 \geq 3$$$
- $$$\operatorname{min}(4, 3, 2) = 2, \operatorname{mex}(1, 0) = 2$$$. $$$2 \geq 2$$$
- $$$\operatorname{min}(4, 3, 2, 1) = 1, \operatorname{mex}(0) = 1$$$. $$$1 \geq 1$$$

In the second test case, the sequence $$$[4, 3, 3, 2, 1, 0]$$$ is not magical, since $$$\operatorname{min}(4, 3) = 3, \operatorname{mex}(3, 2, 1, 0) = 4$$$, $$$3 < 4$$$. However, the subsequence $$$[4, 3, 2, 1, 0]$$$ of this sequence is magical, so the answer is $$$5$$$.

Example input:
8
5
4 3 2 1 0
6
4 3 3 2 1 0
4
2 0 1 2
1
777
4
1000000000 1 7 9
2
0 1
2
1 2
4
0 1 0 1

Example output:
5
5
3
1
4
2
2
3

Editorial:
Note that for those suffixes where there is no number $$$0$$$, $$$\operatorname{mex}$$$ will be equal to $$$0$$$, and thus the condition will be satisfied, since at least on the left side it is definitely $$$\geq 0$$$. That is, any array without zeros is magical.
However, if there are at least two zeros in the array, it can no longer be magical, since we can consider a prefix containing one zero but not containing the second: the minimum on such a prefix is equal to $$$0$$$, while $$$\operatorname{mex}$$$ on the corresponding suffix will definitely be $$$>0$$$, and the condition will not be satisfied.
Thus, we know for sure that the answer is either $$$n - cnt_0$$$ or $$$n - cnt_0 + 1$$$, where $$$cnt_0$$$ is the number of $$$a_i=0$$$. Since we can choose a subsequence without zeros of length $$$n - cnt_0$$$, it will definitely be magical. However, any subsequence of length $$$>n - cnt_0 + 1$$$ must contain at least two zeros and cannot be magical.
Therefore, we only need to determine when the answer is equal to $$$n - cnt_0 + 1$$$. In this case, we must take a subsequence with exactly one zero, since again, sequences with at least two zeros are definitely not magical. It is not difficult to understand that it is optimal to take the leftmost zero in the subsequence, as the condition $$$\min \geq \operatorname{mex}$$$ will be guaranteed to be satisfied for prefixes containing a single zero.
Thus, the solution looks as follows:
• If there are no zeros in the array, the answer is $$$n$$$.
• Otherwise, we need to choose a subsequence consisting of the leftmost zero and all non-zero elements of the sequence.
• Explicitly check whether it is magical (this can be easily done in $$$O(n)$$$, calculating prefix $$$\min$$$ and suffix $$$\operatorname{mex}$$$ is a well-known problem). If yes, the answer is: $$$n - cnt_0 + 1$$$.
• Otherwise, the answer is $$$n - cnt_0$$$, and a subsequence of all non-zero elements will suffice.