P7650 [BalticOI 2007] Ranklist Sorting (Day 1)

In a contest, you are given the scores of several players. Your task is to create a ranklist of the players sorted by decreasing score. Unfortunately, the data structure used for the ranklist supports only one operation: move a player from position $i$ to position $j$ without changing the relative order of the other players. If $i > j$, then the players in positions between $j$ and $i - 1$ increase their positions by $1$; otherwise, if $i < j$, then the players in positions between $i + 1$ and $j$ decrease their positions by $1$. This operation takes $i$ steps to locate the player to be moved, and $j$ steps to locate the position to move him or her to, so the total cost of moving a player from position $i$ to position $j$ is $i + j$. Positions are numbered starting from $1$. Determine a sequence of moves to create the ranklist such that the sum of move costs is minimized.

The first line contains an integer $n$, the number of players. Each of the next $n$ lines contains a non-negative integer $s_i$, the score of a player in the current order. You may assume that all scores are distinct.

Output the number of moves used to create the ranklist on the first line. The following lines should specify the moves in the order they are applied. Each move should be described on one line containing two integers $i$ and $j$, meaning that the player at position $i$ is moved to position $j$. The numbers $i$ and $j$ must be separated by a single space.

#### Constraints For $30 \%$ of the testdata, $n \le 10$, $0 \le s_i \le 10^6$. For $100 \%$ of the testdata, $2 \le n \le 10^3$, $0 \le s_i \le 10^6$. #### Notes From [Baltic Olympiad in Informatics 2007](https://www.boi2007.de/en/welcome), [Day 1:sorting](https://www.boi2007.de/tasks/sorting.pdf). Translated and organized by @[求学的企鹅](/user/271784). Translated by ChatGPT 5