2 seconds
256 megabytes
standard input
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 2m≤n2�≤�.
- Subtract 11 from ai�� for all integers i�, such that 1≤i≤2m1≤�≤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 ai≤ai+1��≤��+1 for all integers i� such that 1≤i≤n−11≤�≤�−1.
The first line contains a single integer t� (1≤t≤1041≤�≤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� (1≤n≤201≤�≤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� (0≤ai≤10000≤��≤1000).
For each test case, output “YES” if the array can be sorted, and “NO” otherwise.
YES YES YES NO NO NO YES YES
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.