Optimal Ranking Table Reordering

In a contest, you are given the scores of several contestants. Your task is to produce a ranking table where the contestants are sorted in descending order of their scores. However, the only allowed operation on the data structure is to move a contestant from position \( i \) to position \( j \) without changing the relative order of the other contestants.

If \( i > j \), the contestants between positions \( j \) and \( i-1 \) each shift one position to the right. If \( i < j \), the contestants between positions \( i+1 \) and \( j \) each shift one position to the left.

The cost for moving a contestant from position \( i \) to \( j \) is given by \( i+j \). Positions are 1-indexed.

Your goal is to determine a sequence of moves to transform the initial ranking into the correct descending order while minimizing the total cost.

Input Format: The first line contains an integer \( n \) denoting the number of contestants. The next line contains \( n \) space-separated integers representing the contestants' scores in their initial order.

Output Format: On the first line, output the minimal total cost of the operations. On the second line, output an integer \( m \) denoting the number of move operations. The following \( m \) lines each contain two integers \( i \) and \( j \) representing a move from position \( i \) to position \( j \).

Note: When scores are equal, the original relative order is maintained.

inputFormat

The input begins with a single integer \( n \) (the number of contestants). The next line contains \( n \) space-separated integers representing the scores of the contestants.

outputFormat

Output the minimal total cost on the first line. On the second line, output the number of moves \( m \). Each of the next \( m \) lines should contain two integers \( i \) and \( j \) representing a move from position \( i \) to position \( j \).

sample

3
5 4 3

0
0