Score : $1400$ points

Problem Statement

In this problem, a "permutation" always means a permutation of $(1,2,\cdots,N)$.

For two permutations $p$ and $q$, let us define the distance between them, $d(p,q)$, as follows.

• Consider making $p$ equal $q$ by repeatedly swapping two adjacent terms in $p$. Let $d(p,q)$ be the minimum number of swaps required here.

Additionally, for a permutation $x$, let us define another permutation $f(x)$ as follows.

• Let $y=(1,2,\cdots,N)$. Consider permutations $z$ such that $d(x,z) \leq d(y,z)$. Let $f(x)$ be the lexicographically smallest of those permutations.

For example, when $x=(2,3,1)$, the permutations $z$ such that $d(x,z) \leq d(y,z)$ are $z=(2,1,3),(2,3,1),(3,1,2),(3,2,1)$. The lexicographically smallest of them is $(2,1,3)$, so we have $f(x)=(2,1,3)$.

You are given a permutation $A=(A_1,A_2,\cdots,A_N)$. Determine whether there is a permutation $x$ such that $f(x)=A$.

Solve $T$ test cases for each input file.

Constraints

• $1 \leq T \leq 150000$
• $2 \leq N \leq 300000$
• $(A_1,A_2,\cdots,A_N)$ is a permutation of $(1,2,\cdots,N)$.
• 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 there is a permutation $x$ such that $f(x)=A$, and No otherwise.

2
2
1 2
2
2 1

Yes
Yes

For instance, when $A=(2,1)$, one can let $x=(2,1)$ to satisfy $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

For instance, when $A=(2,3,1)$, one can let $x=(3,2,1)$ to satisfy $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