{"raw_statement":[{"iden":"background","content":"**本题与 Easy Version 的区别为本题需判断方案的合法性。**\n\n**保证本题所有的测试点时空限制均为 std 的 $2.5$ 倍及以上**。\n"},{"iden":"statement","content":"\n定义 $\\operatorname{mex}(x, y)$ 表示在集合 $\\{x, y\\}$ 中最小的未出现的 **自然数**。例如，$\\operatorname{mex}(1, 5) = 0$，$\\operatorname{mex}(3, 0) = 1$。\n\n继而，我们定义对自然数序列 $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\n一个长度为 $n$ 的整数序列 $a_1\\dots a_n$，满足 $0 \\leq a_i \\leq 10^9$；然后依次对它进行 $n - 1$ 次操作。显然最终序列 $a$ 只会剩下一个数，定义这最终一个数的值成为 **该序列的价值**，记为 $f(a)$。\n\n请问对于给定的 $n$ 和 $a$ 序列，是否对于所有长度为 $n$ 的自然数序列 $b$，$f(a)\\ge f(b)$。\n"},{"iden":"input","content":"**本题有多组数据。**\n\n第一行一个正整数 $T$，表示数据组数。\n\n对于每组数据，第一行一个正整数 $n$。\n\n接下来 $n$ 个整数，表示序列 $a$。"},{"iden":"output","content":"对于每组数据，一行一个字符串 `Yes` 或 `No`。"},{"iden":"note","content":"## 提示\n\n### 样例解释\n\n对于 $n = 2$，$f(a)=2$。可以证明，对于所有长度为 $2$ 的 $b$ 序列满足 $f(b)\\le 2$。\n\n对于 $n = 3$，$f(a)=0$，存在序列 $b=[114,514,1919]$，$f(b)=1>0$。\n\n### 数据规模与约定\n\n**「本题采用捆绑测试」**\n\n| $\\text{Subtask}$ | $\\sum n \\le$|  特殊性质  | 总分值 |\n| :--------------: | :-----: |:-----: | :--------: |\n|       $1$        |  $10^3$ | 无| $10$ |\n$2$        | $5\\cdot 10^5$  | $\\text{A}$ | $5$ |\n|       $3$        | $5\\cdot 10^5$  | $\\text{B}$ | $10$ |\n|       $4$        | $5\\cdot 10^5$ | $a_i< 2$ | $15$ |\n|       $5$        | $10^6$ | 无 | $20$ |\n|       $6$        | $3\\cdot 10^6$ |     无     | $40$ |\n\n特殊性质 $\\text{A}$：保证 $a_i=i$。\n\n特殊性质 $\\text{B}$：保证 $a_i=i\\bmod 3$。\n\n对于所有数据，保证 $1 \\leq T \\leq 10^4$，$n > 1$，$\\sum n \\leq 3\\cdot 10^6$。"}],"translated_statement":null,"sample_group":[["2\n2\n0 1\n3\n1 0 2","Yes\nNo"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}