You are given an array of integers. In one operation, you do the following:
- Choose a non-negative integer , such that .
- Subtract from for all integers , such that .
Can you sort the array in non-decreasing order by performing some number (possibly zero) of operations?
An array is considered non-decreasing iffor all integers such that .
The first line contains a single integer( ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer( ) — the length of array .
The second line of each test case containsintegers — the integers in array ( ).
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 choosetwice to get the array . Then, we can choose once and get the sorted in non-decreasing order array .
In the third test case, we can chooseonce and get the array . Then, we can choose twice and get the array . After that, we can choose once and get the sorted in non-decreasing order array .
For the fourth and fifth test case, it can be shown that the array could not be sorted using these operations.