Improve the Permutation

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Sergey thinks that some permutations are better than other permutations. He thinks that the permutations with the smaller number of inversions are nicer than the ones with the bigger number of inversions. So the smaller the number of inversions is, the nicer is the permutation.
Sergey has a permutation A which he wants to make as nice as possible. This is kind of special permutation, because initially it doesn't have any index i such that A_{i} = i (Assume 1based indexing). For making it nicer, he can swap two adjacent numbers in this permutation, but only if both of them are not on their places (i.e. if you swap A_{i} and A_{i+1}, then A_{i} ≠ i and A_{i+1} ≠ i+1 should be held). He wants to perform such operation multiple times to make the number of inversions in the permutation as small as possible.
Making the permutation the nicest of the possible ones has turned out to be a complicated problem, so Sergey asks you to help him and to provide any sequence of the allowed swaps that would lead him to obtaining the nicest permutation. Since Sergey is quite eager to see the way to improve his permutation, he wants the sequence to be not longer than 2 × N^{2}. It can be proved that such sequence can be found under this restriction.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the amount of numbers in the permutation.
The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the permutation itself.
Output
For each test case, output an answer in the following format:
 The first line should contain a single integer C denoting the number of swap operations.
 On the following line, output C spaceseparated integers D_{j} denoting the swap of the D_{j}^{th} and the (D_{j}+1)^{th} number in the permutation (1indexed).
The restrictions for the output sequence are:
 1 ≤ C ≤ 2 × N^{2}
 1 ≤ D_{j} < N
Constraints
 A is a permutation.
 1 ≤ A_{i} ≤ N
 A_{i} ≠ i
Subtasks
 Subtask #1 (23 points): 1 ≤ T ≤ 10, 1 ≤ N ≤ 5
 Subtask #2 (77 points): 1 ≤ T ≤ 50, 1 ≤ N ≤ 50
Example
Input: 1 4 4 3 2 1 Output: 6 1 3 2 3 1 2
Explanation
Example case 1. Let's perform these operations onebyone. The positions having A_{i} = i will be highlighted in bold:
 Initially we have A = (4, 3, 2, 1)
 Then we swap A_{1} with A_{2}, obtaining A = (3, 4, 2, 1)
 Then we swap A_{3} with A_{4}, obtaining A = (3, 4, 1, 2)
 Then we swap A_{2} with A_{3}, obtaining A = (3, 1, 4, 2)
 Then we swap A_{3} with A_{4}, obtaining A = (3, 1, 2, 4)
 Then we swap A_{1} with A_{2}, obtaining A = (1, 3, 2, 4)
 Finally we swap A_{2} with A_{3}, obtaining A = (1, 2, 3, 4)
This way we've obtained the permutation with zero inversions. Obviously, this is the nicest possible permutation in this test case.
Author:  xcwgf666 
Tester:  errichto 
Editorial  https://discuss.codechef.com/problems/IMPROVE 
Tags  ltime44, mediumhard, permutation, xcwgf666 
Date Added:  13012017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 