分数: 900 点
问题陈述
有 N 圆周上的顶点。 顶点已编号 1 to N 按顺时针顺序排列,顶点 上面写着 i 有一个整数 上面写着 A_i ,哪里 A_i is 1, 2, 3,或 4。在这里, A 包含每个 1, 2, 3,和 4 至少一次。
考虑通过添加来创建一棵树 N-1 连接这些的边缘 N 顶点。 这里,必须满足以下条件。
-
如果顶点 x 和 y 通过边直接连接, |A_x-A_y|=1.
-
当将边绘制为线段时,除了端点之外,没有两条边相交。
例如下图所示是一棵满足条件的树:

判断是否可以构建满足条件的树。
解决 T 每个输入文件的测试用例。 一个输入文件中的
约束
- 1 \leq T \leq 75000
- 4 \leq N \leq 300000
- 1 \leq A_i \leq 4
- A 包含每个 1, 2, 3,和 4 至少一次。
- 总和 N 不超过 300000.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例的格式如下:
N A_1 A_2 \cdots A_N
输出
对于每种情况,打印 Yes 如果可以构建满足条件的树,并且 No 否则。
示例输入 1
3 4 1 2 3 4 4 1 3 4 2 4 1 4 2 3
示例输出 1
Yes Yes No
示例输入 2
3 8 4 2 3 4 1 2 2 1 8 3 2 2 3 1 3 3 4 8 2 3 3 2 1 4 1 4
示例输出 2
Yes Yes No
第一个测试用例对应于问题陈述中的图。