问题陈述

在这个问题中，“排列”始终表示 $(1,2,\cdots,N)$ 的排列。

对于两个排列 $p$ 和 $q$，我们定义它们之间的距离 $d(p,q)$ 如下。

• 考虑通过反复交换 $p$ 中相邻的两个项使其等于 $q$。令 $d(p,q)$ 为此过程所需的最小交换次数。

此外，对于一个排列 $x$，我们如下定义另一个排列 $f(x)$。

• 令 $y=(1,2,\cdots,N)$。考虑满足 $d(x,z) \leq d(y,z)$ 的排列 $z$。令 $f(x)$ 为其中词典序最小的排列。

例如，当 $x=(2,3,1)$ 时，满足 $d(x,z) \leq d(y,z)$ 的排列 $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)$。确定是否存在一个排列 $x$，使得 $f(x)=A$。

对于每个输入文件，解决 $T$ 个测试案例。

关于序列的词典序是什么？

这里描述的算法确定了不同序列 $S$ 和 $T$ 之间的词典序。

下面，令 $S_i$ 表示 $S$ 的第 $i$ 个元素。此外，令 $S \lt T$ 和 $S \gt T$ 分别表示 “$S$ 词典序小于 $T$” 和 “$S$ 词典序大于 $T$”。

1. 令 $L$ 为 $S$ 和 $T$ 中较短的序列的长度。对于每个 $i=1,2,\cdots,L$，我们检查 $S_i$ 和 $T_i$ 是否相等。
2. 如果存在 $i$ 使得 $S_i \neq T_i$，令 $j$ 是最小的这样的 $i$，并比较 $S_j$ 和 $T_j$。如果 $S_j$ 小于 $T_j$（作为一个数），我们得出 $S \lt T$ 并退出；如果 $S_j$ 大于 $T_j$，我们得出 $S \gt T$ 并退出。
3. 如果不存在 $i$ 使得 $S_i \neq T_i$，比较 $S$ 和 $T$ 的长度。如果 $S$ 的长度小于 $T$，我们得出 $S \lt T$ 并退出；如果 $S$ 的长度大于 $T$，我们得出 $S \gt T$ 并退出。

约束条件

• $1 \leq T \leq 150000$
• $2 \leq N \leq 300000$
• $(A_1,A_2,\cdots,A_N)$ 是 $(1,2,\cdots,N)$ 的排列。
• 一个输入文件中 $N$ 的总和不超过 $300000$。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

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

每个案例的格式如下：

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

输出

对于每个案例，如果存在一个排列 $x$，使得 $f(x)=A$，则打印 Yes，否则打印 No。

样例输入 1

2
2
1 2
2
2 1

样例输出 1

Yes
Yes

例如，当 $A=(2,1)$ 时，可以让 $x=(2,1)$ 以满足 $f(x)=A$。

样例输入 2

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

样例输出 2

Yes
Yes
Yes
Yes
No
No

例如，当 $A=(2,3,1)$ 时，可以让 $x=(3,2,1)$ 以满足 $f(x)=A$。

样例输入 3

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

样例输出 3

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