Triple Inversions Solution codechef
For a permutation of the integers to , we define a new array of length as follows:
- For inversions in the subarray , i.e, the number of inversions in the array . , denotes the number of
You are given an arrayof length , all of whose elements lie between and . Does there exist a permutation of length such that ?
- The first line of input will contain one integer , the number of test cases. The description of test cases follows.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer , the size of .
- The second line of each test case contains space-separated integers — the values of .
For each test case, output in a single line the answer —if a permutation that satisfies the given conditions exists, and otherwise.
The output is not case sensitive, so for example the strings, etc. will all be treated as correct.
- The sum of over all test cases doesn’t exceed
Sample Input 1
4 4 0 1 3 2 4 0 1 2 3 4 0 0 0 0 5 0 1 2 1 0
Sample Output 1
YES NO YES NO
Test case: Consider . It can be verified that . There are other permutations which give the same array — for example and .
Test case: It can be verified that no permutation of length has .
Test case: The only permutation that satisfies the condition is .
Test case: It can be verified that no permutation of length has