CF2031B Penchick and Satay Sticks

Penchick 和他的朋友 Kohane 正在印度尼西亚旅游，他们的下一站是泗水！ 在泗水热闹的美食摊上，Kohane 买了 $n$ 根沙爹串，并将它们排成一排，第 $i$ 根沙爹串的长度为 $p_i$。已知 $p$ 是一个长度为 $n$ 的排列 $^{\text{∗}}$。 Penchick 想要将沙爹串按长度递增的顺序排列，使得对于每个 $1\le i\le n$，都有 $p_i=i$。为了增加趣味，他们制定了一个规则：他们只能交换长度恰好相差 $1$ 的相邻沙爹串。具体来说，他们可以进行如下操作任意次（包括零次）： - 选择一个下标 $i$（$1\le i\le n-1$），满足 $|p_{i+1}-p_i|=1$； - 交换 $p_i$ 和 $p_{i+1}$。 请判断是否可以通过上述操作将排列 $p$（即沙爹串）排序。 $^{\text{∗}}$ 长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。

每组测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 2\cdot 10^5$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$），表示沙爹串的数量。 每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$），表示沙爹串的长度排列 $p$。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，如果可以通过上述操作将排列 $p$ 排序，输出 "YES"；否则输出 "NO"。 你可以用任意大小写输出答案（如 "yEs"、"yes"、"Yes"、"YES" 都会被认为是肯定回答）。

在第一个测试用例中，我们可以对排列 $p = [2, 1, 3, 4]$ 在下标 $1$ 处进行一次操作（$|p_2 - p_1| = |1 - 2| = 1$），得到 $p = [1, 2, 3, 4]$，从而完成排序。 在第二个测试用例中，可以证明无法通过操作将排列 $p = [4, 2, 3, 1]$ 排序。以下是对该排列可以进行的一系列操作示例： - 选择 $i = 2$（$|p_3 - p_2| = |3 - 2| = 1$），得到 $p = [4, 3, 2, 1]$； - 选择 $i = 1$（$|p_2 - p_1| = |3 - 4| = 1$），得到 $p = [3, 4, 2, 1]$； - 选择 $i = 3$（$|p_4 - p_3| = |1 - 2| = 1$），得到 $p = [3, 4, 1, 2]$。 遗憾的是，经过这些操作后，排列 $p$ 仍未排序。 由 ChatGPT 4.1 翻译