配点 : $1400$ 点

問題文

この問題では，順列と言った際には，$(1,2,\cdots,N)$ の順列を指すものとします．

$2$ つの順列 $p,q$ に対し，それらの距離 $d(p,q)$ を次のように定義します．

• $p$ の中で隣接 $2$ 項を swap することを繰り返し，$p$ を $q$ に一致させることを考える．この時必要な最小の操作回数を $d(p,q)$ とする．

さらに，順列 $x$ に対し，順列 $f(x)$ を次のように定義します．

• $y=(1,2,\cdots,N)$ とする．ここで，順列 $z$ であって，$d(x,z) \leq d(y,z)$ を満たすものを考える． これらの中で辞書順最小のものを $f(x)$ とする．

例えば，$x=(2,3,1)$ の場合，$d(x,z) \leq d(y,z)$ を満たす順列としては，$z=(2,1,3),(2,3,1),(3,1,2),(3,2,1)$ が考えられます． このうち辞書順最小なのは $(2,1,3)$ なので， $f(x)=(2,1,3)$ となります．

順列 $A=(A_1,A_2,\cdots,A_N)$ が与えられます． $f(x)=A$ を満たす順列 $x$ が存在するかどうか判定してください．

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

制約

• $1 \leq T \leq 150000$
• $2 \leq N \leq 300000$
• $(A_1,A_2,\cdots,A_N)$ は $(1,2,\cdots,N)$ の順列
• $1$ つの入力ファイルにつき，$N$ の総和は $300000$ を超えない
• 入力される値はすべて整数である

入力

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

$T$

$case_1$

$case_2$

$\vdots$

$case_T$

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

$N$

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

出力

各ケースに対し，$f(x)=A$ を満たす順列 $x$ が存在するならば Yes を，存在しないならば No を出力せよ．

2
2
1 2
2
2 1

Yes
Yes

例えば $A=(2,1)$ の場合は，$x=(2,1)$ とすると $f(x)=A$ となります．

6
3
1 2 3
3
1 3 2
3
2 1 3
3
2 3 1
3
3 1 2
3
3 2 1

Yes
Yes
Yes
Yes
No
No

例えば $A=(2,3,1)$ の場合は，$x=(3,2,1)$ とすると，$f(x)=A$ となります．

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

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No