Given a 1-indexed list of distinct integers, define operation to remove the integer currently at index and insert it so that it ends up at index , retaining the relative order of all other integers.
Operation incurs cost . Using only this operation, sort the integers in decreasing order, minimizing the sum of the costs incurred.
All are distinct.
For at most 30% of marks, .
The first line will contain a single integer, .
Each of the following lines contains a single integer, , the list of integers in order.
Print on the first line a single integer, containing the number of moves needed to sort the integers.
On each of the next lines, print one of the move operations in the format
i j. The operations should be printed in the
order that they will be executed.
If there are multiple optimal ways to operate on the list, output any such way.
5 20 30 5 15 10
2 2 1 3 5