← 返回题目列表

Codeforces · 2031/B

B. Penchick 和沙爹棒

中文机器翻译题面 查看原题

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$$$ 进行排序,从而使沙爹棒排序。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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”将被识别为肯定响应。

示例

输入 #1

2
4
2 1 3 4
4
4 2 3 1

输出 #1

YES
NO

注意

在第一个测试用例中,我们可以通过对索引 $$$1$$$ ($$$|p_2 - p_1| = |1 - 2| = 1$$$) 执行操作来对排列 $$$p = [2, 1, 3, 4]$$$ 进行排序,得到 $$$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$$$ 仍然未排序。