← 返回题目列表

AtCoder · agc058_c

C. 平面树

中文机器翻译题面 查看原题

分数: 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.

  • 当将边绘制为线段时,除了端点之外,没有两条边相交。

例如下图所示是一棵满足条件的树:

figure1

判断是否可以构建满足条件的树。

解决 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

第一个测试用例对应于问题陈述中的图。