310809: CF1891A. Sorting with Twos

A. Sorting with Twostime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

Input

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

Output

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

ExampleInput

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

Output

YES
YES
YES
NO
NO
NO
YES
YES

Note

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.

题目大意：
这个题目是关于给定一个整数数组，通过一系列的操作来对其进行非降序排序的问题。操作规则如下：
1. 选择一个非负整数 m，使得 2^m ≤ n。
2. 将数组中所有满足 1 ≤ i ≤ 2^m 的 a_i 元素减去 1。

你需要判断是否可以通过执行零次或多次这样的操作来将数组排序为非降序。非降序指的是对于所有 1 ≤ i ≤ n - 1 的整数 i，a_i ≤ a_{i + 1}。

输入输出数据格式：
输入：
- 第一行包含一个整数 t (1 ≤ t ≤ 10^4)，表示测试用例的数量。
- 每个测试用例的第一行包含一个整数 n (1 ≤ n ≤ 20)，表示数组 a 的长度。
- 每个测试用例的第二行包含 n 个整数 a_1, a_2, ..., a_n，表示数组 a 的元素 (0 ≤ a_i ≤ 1000)。

输出：
- 对于每个测试用例，如果可以通过上述操作将数组排序为非降序，输出 "YES"，否则输出 "NO"。题目大意： 这个题目是关于给定一个整数数组，通过一系列的操作来对其进行非降序排序的问题。操作规则如下： 1. 选择一个非负整数 m，使得 2^m ≤ n。 2. 将数组中所有满足 1 ≤ i ≤ 2^m 的 a_i 元素减去 1。 你需要判断是否可以通过执行零次或多次这样的操作来将数组排序为非降序。非降序指的是对于所有 1 ≤ i ≤ n - 1 的整数 i，a_i ≤ a_{i + 1}。 输入输出数据格式： 输入： - 第一行包含一个整数 t (1 ≤ t ≤ 10^4)，表示测试用例的数量。 - 每个测试用例的第一行包含一个整数 n (1 ≤ n ≤ 20)，表示数组 a 的长度。 - 每个测试用例的第二行包含 n 个整数 a_1, a_2, ..., a_n，表示数组 a 的元素 (0 ≤ a_i ≤ 1000)。 输出： - 对于每个测试用例，如果可以通过上述操作将数组排序为非降序，输出 "YES"，否则输出 "NO"。