P10370 "LAOI-4" Mex Tower (Hard ver.)

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

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

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

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

### 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."** | $\text{Subtask}$ | $\sum n \le$ | Special Property | Total Score | | :--------------: | :----------: | :--------------: | :---------: | | $1$ | $10^3$ | None | $10$ | | $2$ | $5\cdot 10^5$| $\text{A}$ | $5$ | | $3$ | $5\cdot 10^5$| $\text{B}$ | $10$ | | $4$ | $5\cdot 10^5$| $a_i< 2$ | $15$ | | $5$ | $10^6$ | None | $20$ | | $6$ | $3\cdot 10^6$| None | $40$ | 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