C - Planar Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

ある円環上に N 個の頂点が並んでいます． 頂点には時計回りに 1 から N の番号がついており，頂点 i には整数 A_i が書かれています． ここで，A_i は 1,2,3,4 のいずれかです． また A は 1,2,3,4 をそれぞれ 1 つ以上含みます．

これらの N 個の頂点を結ぶ辺を N-1 本追加し，木を作ることを考えます． ただしこの時，以下の条件を満たす必要があります．

  • 頂点 x,y が直接辺で結ばれているならば，|A_x-A_y|=1 である．

  • 追加した辺を線分として描いた時，どの 2 つも端点以外で交わらない．

例えば，以下の図は条件を満たす木の例です．

figure1

条件を満たすような木を作ることが可能かどうか判定してください．

1 つの入力ファイルにつき，T 個のテストケースを解いてください．

制約

  • 1 \leq T \leq 75000
  • 4 \leq N \leq 300000
  • 1 \leq A_i \leq 4
  • A は 1,2,3,4 をそれぞれ 1 つ以上含む
  • 1 つの入力ファイルにつき，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

最初のテストケースは，問題文中の図に対応しています．

Score : 900 points

Problem Statement

There are N vertices on a circumference. The vertices are numbered 1 to N in clockwise order, and Vertex i has an integer A_i written on it, where A_i is 1, 2, 3, or 4. Here, A contains each of 1, 2, 3, and 4 at least once.

Consider making a tree by adding N-1 edges connecting these N vertices. Here, the following conditions must be satisfied.

  • If Vertices x and y are directly connected by an edge, |A_x-A_y|=1.

  • When the edges are drawn as segments, no two of them intersect except at an endpoint.

For instance, the figure below shows a tree that satisfies the conditions:

figure1

Determine whether it is possible to construct a tree that satisfies the conditions.

Solve T test cases for each input file.

Constraints

  • 1 \leq T \leq 75000
  • 4 \leq N \leq 300000
  • 1 \leq A_i \leq 4
  • A contains each of 1, 2, 3, and 4 at least once.
  • The sum of N in one input file does not exceed 300000.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is in the following format:

N
A_1 A_2 \cdots A_N

Output

For each case, print Yes if it is possible to construct a tree that satisfies the conditions, and No otherwise.

Sample Input 1

3
4
1 2 3 4
4
1 3 4 2
4
1 4 2 3

Sample Output 1

Yes
Yes
No

Sample Input 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

Sample Output 2

Yes
Yes
No

The first test case corresponds to the figure in the Problem Statement.