Physicist S has an array. He wants to sort the array in increasing order. However, as he is very lazy, he will only swap two adjacent elements in the array, and he wishes to have the array sorted in the minimum number of steps.
Help Physicist S by writing a program that tells him how to sort his array.
The first line of input contains a single integer, N, the size of Physicist S's array.
The second line of input contains N integers, representing Physicist S's array.
The first line of output should contain a single integer, ans, the minimum number of swaps required to sort the array.
The next ans lines of input should contain one integer each, i, denoting a swap between the ith and (i + 1)th element. If 1 ≤ i < N is not satisfied, you will receive a wrong answer verdict.
For all test cases, 1 ≤ N ≤ 100. All elements in the array are distinct and are integers from 1 to N.
If the sequence of swaps you present does not sort the array, you will not receive any points.
Otherwise, your score for that test case is given by 50 + 50 * opt / ans, where opt is the optimal number of swaps.
Your final score is the minimum score for all test cases.
3 3 1 2
2 1 2
Swapping the 1st and 2nd elements, followed by the 2nd and 3rd elements, sorts the array. This is the minimum number of swaps.