给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。在一项操作中,您执行以下操作:
- 选择一个非负整数 $$$m$$$,使得 $$$2^m \leq n$$$。
- 对于所有整数 $$$i$$$,从 $$$a_i$$$ 中减去 $$$1$$$,使得 $$$1 \leq i \leq 2^m$$$。
您可以通过执行一定数量(可能为零)的操作来按非降序对数组进行排序吗?
如果对于所有整数 $$$i$$$ $$$a_i \leq a_{i + 1}$$$ 使得 $$$1 \leq i \leq n - 1$$$,则认为数组是非递减的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 20$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ — 数组 $$$a$$$ 中的整数 ($$$0 \leq a_i \leq 1000$$$)。
输出
对于每个测试用例,如果数组可以排序,则输出“YES”,否则输出“NO”。
示例
输入 #1
8 5 1 2 3 4 5 5 6 5 3 4 4 9 6 5 5 7 5 6 6 8 7 4 4 3 2 1 6 2 2 4 5 3 2 8 1 3 17 19 27 57 179 13 5 3 17 57 179 92 10 1 2 3 4 0 6 7 8 9 10
输出 #1
YES YES YES NO NO NO YES YES
注意
在第一个测试用例中,数组已经按非降序排序,因此我们不必执行任何操作。
在第二个测试用例中,我们可以选择 $$$m = 1$$$ 两次来得到数组 $$$[4, 3, 3, 4, 4]$$$。然后,我们可以选择一次$$$m = 0$$$,得到按非降序排序的数组$$$[3, 3, 3, 4, 4]$$$。
在第三个测试用例中,我们可以选择 $$$m = 0$$$ 一次,得到数组 $$$[5, 5, 5, 7, 5, 6, 6, 8, 7]$$$。然后,我们可以选择$$$m = 2$$$两次,得到数组$$$[3, 3, 3, 5, 5, 6, 6, 8, 7]$$$。之后,我们可以选择一次$$$m = 3$$$,得到按非降序排序的数组$$$[2, 2, 2, 4, 4, 5, 5, 7, 7]$$$。
对于第四个和第五个测试用例,可以表明无法使用这些操作对数组进行排序。