CF1891A.Sorting with Twos

You are given an array of integers $a_1, a_2, \ldots, a_n$. In one operation, you do the following:

• Choose a non-negative integer $m$, such that $2^m \leq n$.
• Subtract $1$ from $a_i$ for all integers $i$, such that $1 \leq i \leq 2^m$.

Can you sort the array in non-decreasing order by performing some number (possibly zero) of operations?

An array is considered non-decreasing if $a_i \leq a_{i + 1}$ for all integers $i$ such that $1 \leq i \leq n - 1$.

给你一个整数数组 $a_1, a_2, \ldots, a_n$。每次操作中，你需要执行以下步骤：

• 选择一个非负整数 $m$，使得 $2^m \leq n$；
• 对所有满足 $1 \leq i \leq 2^m$ 的整数 $i$，将 $a_i$ 减去 $1$。

你能否通过执行若干次（可能为零次）上述操作，将该数组变为非递减序列？

若对所有满足 $1 \leq i \leq n - 1$ 的整数 $i$，均有 $a_i \leq a_{i + 1}$，则称该数组为非递减序列。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 20$) — the length of array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ — the integers in array $a$ ($0 \leq a_i \leq 1000$).

第一行包含一个整数 $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$）。

For each test case, output "YES" if the array can be sorted, and "NO" otherwise.

对于每个测试用例，如果数组可以被排序，则输出 “YES”，否则输出 “NO”。

In the first test case, the array is already sorted in non-decreasing order, so we don't have to perform any operations.

In the second test case, we can choose $m = 1$ twice to get the array $[4, 3, 3, 4, 4]$. Then, we can choose $m = 0$ once and get the sorted in non-decreasing order array $[3, 3, 3, 4, 4]$.

In the third test case, we can choose $m = 0$ once and get the array $[5, 5, 5, 7, 5, 6, 6, 8, 7]$. Then, we can choose $m = 2$ twice and get the array $[3, 3, 3, 5, 5, 6, 6, 8, 7]$. After that, we can choose $m = 3$ once and get the sorted in non-decreasing order array $[2, 2, 2, 4, 4, 5, 5, 7, 7]$.

For the fourth and fifth test case, it can be shown that the array could not be sorted using these operations.

在第一个测试用例中，数组已经按非递减顺序排序，因此我们无需执行任何操作。

在第二个测试用例中，我们可以选择 $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]$。

对于第四和第五个测试用例，可以证明无法通过这些操作将数组排序。