Background

The difference from the Easy Version is that this problem requires checking whether the solution is valid.

It is guaranteed that for all test points in this problem, the time and memory limits are at least $2.5$ times those of the standard solution (std).

Problem Description

Define $\operatorname{mex}(x, y)$ as the smallest non-negative integer that does not appear in the set $\{x, y\}$. For example, $\operatorname{mex}(1, 5) = 0$, and $\operatorname{mex}(3, 0) = 1$.

Next, we define one operation on a non-negative integer sequence $a_1 \dots a_n$ as replacing sequence $a$ with a sequence $a'_1 \dots a'_{n-1}$ of length $\bm{n - 1}$, where $a'_i = \operatorname{mex}(a_i, a_{i+1})$.

Given an integer sequence $a_1 \dots a_n$ of length $n$, where $0 \leq a_i \leq 10^9$, perform the operation $n - 1$ times in order. Obviously, the final sequence $a$ will contain only one number. Define the value of this final number as the value of the sequence, denoted by $f(a)$.

For the given $n$ and sequence $a$, determine whether for all non-negative integer sequences $b$ of length $n$, it holds that $f(a) \ge f(b)$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case, the first line contains a positive integer $n$.

The next line contains $n$ integers, representing the sequence $a$.

Output Format

For each test case, output one string per line: Yes or No.

2
2
0 1
3
1 0 2

Yes
No

Hint

Sample Explanation

For $n = 2$, $f(a)=2$. It can be proven that for all sequences $b$ of length $2$, $f(b)\le 2$.

For $n = 3$, $f(a)=0$. There exists a sequence $b=[114,514,1919]$ with $f(b)=1>0$.

Constraints

"This problem uses bundled tests."

Special Property $\text{A}$: It is guaranteed that $a_i=i$.

Special Property $\text{B}$: It is guaranteed that $a_i=i\bmod 3$.

For all testdata, it is guaranteed that $1 \leq T \leq 10^4$, $n > 1$, and $\sum n \leq 3\cdot 10^6$.

Translated by ChatGPT 5