AT_agc058_e [AGC058E] Nearer Permutation

在本题中，提到“顺序排列”时，指的是 $ (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 $，记为 $ ST $。 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 $，则 $ ST $，算法结束。 3. 若所有 $ S_i=T_i $，则比较 $ S $ 和 $ T $ 的长度，短者字典序小。若 $ S $ 比 $ T $ 短，则 $ ST $，算法结束。

输入以如下格式从标准输入读入。 > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 每个测试用例如下格式： > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

对于每个测试用例，若存在排列 $ x $ 使得 $ f(x)=A $，输出 `Yes`，否则输出 `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 翻译