## Mock CCO '18 Contest 1 Problem 2 - A Sorting Problem

View as PDF

Points: 30 (partial)
Time limit: 0.25s
Memory limit: 16M

Problem type

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.

#### Constraints

All are distinct.

For at most 30% of marks, .

#### Input Specification

The first line will contain a single integer, .

Each of the following lines contains a single integer, , the list of integers in order.

#### Output Specification

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.

#### Sample Input

5
20
30
5
15
10

#### Sample Output

2
2 1
3 5