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.


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


Sample Output

2 1
3 5


There are no comments at the moment.