题目描述

给定一个长度为 $n$ 的排列 $a$。

你可以进行如下操作任意次（可以为零次）：

• 选择一个下标 $i$（$1 \le i \le \frac{n}{2}$），交换 $a_i$ 和 $a_{2i}$。

例如，当 $a=[1,4,2,3,5]$ 时，你可以交换 $a_2$ 和 $a_4$ 使其变为 $[1,3,2,4,5]$，但你不能交换 $a_2$ 和 $a_3$。

请你判断，是否可以通过若干次上述操作将序列 $a$ 排成升序。

一个长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。

输入格式

每组测试数据包含多个测试用例。第一行包含测试用例组数 $t$（$1 \le t \le 10^4$）。接下来是各组测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

第二行包含 $n$ 个不同的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

如果 $a$ 可以升序排列，则输出一行 “YES”。否则输出一行 “NO”。

输出答案时不区分大小写。例如，字符串 "yEs"、"yes" 和 "Yes" 都被视为肯定回答。

样例

2
5
1 4 3 2 5
5
1 4 2 3 5

YES
NO

样例说明

在第一个测试用例中，$a = [1,4,3,2,5]$。你可以通过交换 $a_2$ 和 $a_4$ 将 $a$ 排成升序。因此答案为 “YES”。

在第二个测试用例中，$a = [1,4,2,3,5]$。无论如何都无法排成升序。因此答案为 “NO”。

由 ChatGPT 5 翻译

来源

Codeforces 2195B，英文题名 Heapify 1。