题目背景

本题与 Easy Version 的区别为本题需判断方案的合法性。

保证本题所有的测试点时空限制均为 std 的 $2.5$ 倍及以上。

题目描述

定义 $\operatorname{mex}(x, y)$ 表示在集合 $\{x, y\}$ 中最小的未出现的 自然数。例如，$\operatorname{mex}(1, 5) = 0$，$\operatorname{mex}(3, 0) = 1$。

继而，我们定义对自然数序列 $a_1\dots a_n$ 的一次操作，是将序列 $a$ 替换为 长度为 $\bm{n - 1}$ 的 序列 $a'_1\dots a'_{n-1}$，其中 $a'_i = \operatorname{mex}(a_i, a_{i+1})$。

一个长度为 $n$ 的整数序列 $a_1\dots a_n$，满足 $0 \leq a_i \leq 10^9$；然后依次对它进行 $n - 1$ 次操作。显然最终序列 $a$ 只会剩下一个数，定义这最终一个数的值成为 该序列的价值，记为 $f(a)$。

请问对于给定的 $n$ 和 $a$ 序列，是否对于所有长度为 $n$ 的自然数序列 $b$，$f(a)\ge f(b)$。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行一个正整数 $n$。

接下来 $n$ 个整数，表示序列 $a$。

输出格式

对于每组数据，一行一个字符串 Yes 或 No。

2
2
0 1
3
1 0 2

Yes
No

提示

提示

样例解释

对于 $n = 2$，$f(a)=2$。可以证明，对于所有长度为 $2$ 的 $b$ 序列满足 $f(b)\le 2$。

对于 $n = 3$，$f(a)=0$，存在序列 $b=[114,514,1919]$，$f(b)=1>0$。

数据规模与约定

「本题采用捆绑测试」

特殊性质 $\text{A}$：保证 $a_i=i$。

特殊性质 $\text{B}$：保证 $a_i=i\bmod 3$。

对于所有数据，保证 $1 \leq T \leq 10^4$，$n > 1$，$\sum n \leq 3\cdot 10^6$。