题目描述

在本题中，提到“顺序排列”时，指的是 $(1,2,\cdots,N)$ 的一个排列。

对于两个排列 $p,q$，定义它们的距离 $d(p,q)$ 如下：

• 通过不断交换 $p$ 中相邻的两个元素，将 $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)$，请判断是否存在排列 $x$，使得 $f(x)=A$。

每个输入文件包含 $T$ 个测试用例。

什么是数列的字典序？判断两个不同数列 $S$ 和 $T$ 的大小的算法如下：

记 $S$ 的第 $i$ 个元素为 $S_i$。若 $S$ 的字典序小于 $T$，记为 $S<T$，大于则记为 $S>T$。

1. 取 $S$ 和 $T$ 中较短的长度为 $L$。依次比较 $i=1,2,\dots,L$ 时 $S_i$ 和 $T_i$ 是否相等。
2. 若存在 $S_i\neq T_i$ 的 $i$，取最小的此类 $i$ 为 $j$。若 $S_j$ 小于 $T_j$，则 $S<T$，否则 $S>T$，算法结束。
3. 若所有 $S_i=T_i$，则比较 $S$ 和 $T$ 的长度，短者字典序小。若 $S$ 比 $T$ 短，则 $S<T$，否则 $S>T$，算法结束。

输入格式

输入以如下格式从标准输入读入。

$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

输出

Yes
Yes

样例 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

输出

Yes
Yes
Yes
Yes
No
No

样例 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

输出

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

说明/提示

限制条件

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

样例解释 1

例如 $A=(2,1)$ 时，取 $x=(2,1)$，则 $f(x)=A$。

样例解释 2

例如 $A=(2,3,1)$ 时，取 $x=(3,2,1)$，则 $f(x)=A$。

由 ChatGPT 4.1 翻译