Differential Sorting solution codeforces
You are given an arrayof elements.
Your can perform the following operation no more thantimes: Select three indices and replace with . After the operation, need to be less than .
Your goal is to make the resulting array non-decreasing. If there are multiple solutions, you can output any. If it is impossible to achieve, you should report it as well.
Each test contains multiple test cases. The first line will contain a single integer— the number of test cases. Then test cases follow.
The first line of each test case contains a single integer— the size of the array .
The second line of each test case containsintegers , the elements of .
It is guaranteed that the sum ofover all test cases does not exceed .
For each test case, printin a single line if there is no solution. Otherwise in the first line you should print a single integer — number of operations you performed.
Then the-th of the following lines should contain three integers — description of the -th operation.
If there are multiple solutions, you can output any. Note that you don’t have to minimize the number of operations in this task.
3 5 5 -4 2 -1 2 3 4 3 2 3 -3 -2 -1
2 1 2 3 3 4 5 -1 0
In the first example, the array becomes
after the first operation,
after the second operation.
In the second example, it is impossible to make the array sorted after any sequence of operations.
In the third example, the array is already sorted, so we don’t need to perform any operations.