题目描述

ある円環上に $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$ つも端点以外で交わらない．

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

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

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

输入格式

入力は以下の形式で標準入力から与えられる．

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

各ケースは以下の形式で与えられる．

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

各ケースに対し，条件を満たす木を作ることができるならば Yes を，できないならば No を出力せよ．

题目大意

有 $T$ 组数据 $T(T \leq 75000)$。

每组数据输入一个环，环上的点的个数为 $n(n \leq 300000)$，并且环上每个点有一个权值 $A_i \in \{1,2,3,4\}$，保证每种权值都至少出现一次。环上两个点 $i, j$ 之间能连边当且仅当 $|A_i - A_j| = 1$。

问是否可能连上 $n-1$ 条边后形成一棵树，且树上每条边不在非端点处相交。

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

Yes
Yes
No

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

Yes
Yes
No

提示

制約

• $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$ を超えない
• 入力はすべて整数である

Sample Explanation 2

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