Constructive Problem
Contest: Codeforces Round 866 (Div. 1)
Difficulty rating: 1300
Tags: brute force, greedy

As you know, any problem that does not require the use of complex data structures is considered constructive. You are offered to solve one of such problems.

You are given an array $$$a$$$ of $$$n$$$ non-negative integers. You are allowed to perform the following operation exactly once: choose some non-empty subsegment $$$a_l, a_{l+1}, \ldots, a_r$$$ of the array $$$a$$$ and a non-negative integer $$$k$$$, and assign value $$$k$$$ to all elements of the array on the chosen subsegment.

The task is to find out whether $$$\operatorname{MEX}(a)$$$ can be increased by exactly one by performing such an operation. In other words, if before the operation $$$\operatorname{MEX}(a) = m$$$ held, then after the operation it must hold that $$$\operatorname{MEX}(a) = m + 1$$$.

Recall that $$$\operatorname{MEX}$$$ of a set of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the set $$$c$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50\,000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the number of elements of array $$$a$$$.

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

It is guaranteed that the sum $$$n$$$ over all test cases does not exceed $$$200\,000$$$.

Output format:
For each test case, print "Yes" if you can increase $$$\operatorname{MEX}(a)$$$ by exactly one by performing the operation from the statement exactly once, otherwise print "No".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

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

Note:
In the first test case, $$$\operatorname{MEX}(a) = 0$$$. If you set all elements of $$$a$$$ to $$$0$$$, then $$$\operatorname{MEX}$$$ of the resulting array will be $$$1$$$, and thus will increase by one.

In the second test case, $$$\operatorname{MEX}(a) = 1$$$. If we assign a value of $$$1$$$ to the elements of $$$a$$$ on a subsegment from $$$2$$$ to $$$3$$$, we get an array $$$[0, 1, 1, 0]$$$ for which $$$\operatorname{MEX}$$$ is $$$2$$$, and thus is increased by one compared to the original.

It can be shown that in the third and fourth test cases it is impossible to perform an operation so that the value of $$$\operatorname{MEX}(a)$$$ increases by exactly one.

Example input:
4
3
1 2 1
4
0 2 2 0
4
3 2 0 2
1
0

Example output:
Yes
Yes
No
No

Editorial:
Let the current value of mex equal to $$$m$$$ and the value of mex after performing operation equals to $$$m'$$$. It's easy to see that in the resulting array there should exist element equals to $$$m + 1$$$ (if it doesn't exist, the value of mex won't be equal to $$$m + 1$$$). Also notice that $$$k$$$ should be equal to $$$m$$$ because this value didn't appear in the array before the operation and must appear there after performing the operation. Consider the following cases.
• If there exists such $$$i$$$ that $$$a_i = m + 1$$$, let's find the minimum value $$$l$$$ and the maximum value $$$r$$$ such that $$$a_l = a_r = m + 1$$$. It's easy to see that the performed operation should cover these elements. We already know which value of $$$k$$$ to select. Now notice that there are no profits from using longer segments because $$$m'$$$ is already not greater than $$$m + 1$$$ (there are no elements equal to $$$m + 1$$$) and longer segments may make $$$m'$$$ less.
• If there is no such $$$i$$$ that $$$a_i = m$$$ but there exists $$$i$$$ such that $$$a_i > m + 1$$$, $$$m'$$$ is already not greater than $$$m + 1$$$. Similarly with the previous case, we can find any $$$i$$$ such that $$$a_i > m + 1$$$ and replace $$$a_i$$$ with $$$m$$$.
• In all other cases if there exist two indices $$$i \ne j$$$ such that $$$a_i = a_j$$$, we can replace one of these elements with $$$m$$$. In this case we will make $$$m'$$$ equals to $$$m + 1$$$. If there are no such indices, $$$m$$$ equals to the length of the array and we cannot increment $$$m$$$.
The only thing we have to do after considering cases is to check if the performed operation leads to correct value of $$$m'$$$.
Time complexity: $$$\mathcal{O}(n \log n)$$$.