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

View as PDF

Submit solution


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

Problem type

Given a 1-indexed list of N distinct integers, define operation f(i, j) to remove the integer currently at index i and insert it so that it ends up at index j, retaining the relative order of all other integers.

Operation f(i, j) incurs cost i+j. Using only this operation, sort the integers in decreasing order, minimizing the sum of the costs incurred.

Constraints

2 \le N \le 1000

0 \le l_i \le 10^6

All l_i are distinct.

For at most 30% of marks, N \le 10.

Input Specification

The first line will contain a single integer, N.

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

Output Specification

Print on the first line a single integer, K containing the number of moves needed to sort the integers. On each of the next K 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

Comments

There are no comments at the moment.