A16348. 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$ .

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$ ).

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

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.