给你一个长度为 $$$n$$$$$^{\text{*}}$$$ 的排列 $$$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$$$ 是否可以按升序排序。
$$$^{\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 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$$$可以按升序排序,则输出“是" 在单独的一行上。否则,输出“NO" 在单独的一行上。
任何情况下都可以输出答案。例如,字符串“是", "是的“,和”是”也将被视为积极响应。
示例
输入复制
251 4 3 2 551 4 2 3 5
输出复制
YESNO
注意
在第一个测试用例中,$$$a$$$ 是 $$$[1,4,3,2,5]$$$。您可以通过交换 $$$a_2$$$ 和 $$$a_4$$$ 按升序对 $$$a$$$ 进行排序。因此,答案是“是".
在第二个测试用例中,$$$a$$$ 是 $$$[1,4,2,3,5]$$$。不可能按升序对 $$$a$$$ 进行排序。因此,答案是“NO".