# [SOLUTION] Sorting with Twos Solution Codeforces

A. [SOLUTION] Sorting with Twos Solution Codeforces
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array of integers a1,a2,,an�1,�2,…,��. In one operation, you do the following:

• Choose a non-negative integer m, such that 2mn2�≤�.
• Subtract 11 from ai�� for all integers i, such that 1i2m1≤�≤2�.

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

An array is considered non-decreasing if aiai+1��≤��+1 for all integers i such that 1in11≤�≤�−1.

Input

The first line contains a single integer t (1t1041≤�≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (1n201≤�≤20) — the length of array a.

The second line of each test case contains n integers a1,a2,,an�1,�2,…,�� — the integers in array a (0ai10000≤��≤1000).

Output

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

Example
input

Copy
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

Copy
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�=1 twice to get the array [4,3,3,4,4][4,3,3,4,4]. Then, we can choose m=0�=0 once and get the sorted in non-decreasing order array [3,3,3,4,4][3,3,3,4,4].

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