AT_agc058_c [AGC058C] Planar Tree

在一个圆环上排列着 $N$ 个顶点。顶点按顺时针方向编号为 $1$ 到 $N$，第 $i$ 个顶点上写有整数 $A_i$，其中 $A_i$ 的取值为 $1,2,3,4$ 中的一个。此外，$A$ 中的 $1,2,3,4$ 每个数字都至少出现一次。 现在考虑在这 $N$ 个顶点之间添加 $N-1$ 条边，使其构成一棵树。此时，必须满足以下条件： - 如果顶点 $x$ 和 $y$ 之间直接有边相连，则 $|A_x-A_y|=1$。 - 添加的所有边如果画成线段，则任意两条边除了端点外不会相交。 例如，下图是满足条件的树的一个例子。  请判断是否存在一种方案，能够构造出满足条件的树。 对于每个输入文件，需要解答 $T$ 个测试用例。

输入按以下格式从标准输入读入。 > $T$ > $case_1$ > $case_2$ > $\vdots$ > $case_T$ 每个测试用例的格式如下： > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

对于每个测试用例，如果可以构造出满足条件的树，则输出 `Yes`，否则输出 `No`。

## 限制条件 - $1 \leq T \leq 75000$ - $4 \leq N \leq 300000$ - $1 \leq A_i \leq 4$ - $A$ 中的 $1,2,3,4$ 每个数字都至少出现一次 - 每个输入文件中所有 $N$ 的总和不超过 $300000$ - 输入均为整数 ## 样例解释 2 第一个测试用例对应于题目描述中的图示。 由 ChatGPT 4.1 翻译