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 翻译