Permutation Move Sort

Sort a permutation by moving individual elements while minimizing the declared move cost.

Solution Interface

Submit a zip_project solution. The run command is executed once per case, reads the case from standard input, and writes the answer to standard output. The trusted separated evaluator runs the migrated Frontier-CS Testlib checker against the submitted output and the case's evaluator-only answer or scoring metadata.

Scoring

The leaderboard score is the average checker ratio scaled to 0..100 across official cases. Invalid outputs receive zero for the affected case. The public validation case is intentionally tiny and deterministic; official scoring uses the source-derived Frontier-CS cases packaged as private benchmark data.

Original Statement

OgreSort

You need to sort a permutation v of length n. All elements of the permutation are indexed from 1 to n. The only permitted type of move allows you to take an element from some position x and insert it at another position y, shifting all elements in between by one. The cost of such a move is y. Formally, a move takes an element valued t from position x, “freeing” the index x. We then shift the remaining elements in v, such that the “free” position becomes y. We then put t in the free position at index y. For example, if we have a permutation [4, 3, 2, 1], some of the possible moves: • x = 2, y = 4, the resulting permutation is [4, 2, 1, 3], the cost of the move is 4. • x = 2, y = 1, the resulting permutation is [3, 4, 2, 1], the cost of the move is 1. The final cost is computed as (total cost + 1) * (number of moves + 1). You need to minimize the final cost.

Input The first line contains an integer n — the length of the permutation. The second line contains n integers v1, v2, . . . , vn — the values of the permutation.

Constraints 1 <= n <= 3 * 10^5 1 <= vi <= n, vi != vj for all 1 <= i < j <= n.

Output On the first line, print two numbers min_cost and len_moves — the minimum final cost needed to sort the permutation and the length of the proposed sequence of moves respectively. The next len_moves lines should each contain two integers xk, yk each, signifying that the k-th operation should move the element from position xk to position yk (1 ≤ k ≤ len_moves, 1 <= xk, yk <= n). If several possible sequences of moves exist, you can print any of them.

Scoring You will be graded based on the final costs you give. To be more specific, your answer will be compared to a solution best_answer. Your final score will be calculated as the average of 100 * min(best_answer / your_answer, 1) across all cases.

Time limit: 2 seconds

Memoriy limit: 512 MB

Sample input: 5 2 4 1 3 5 Sample Output: 12 2 4 2 4 1 Sample Explanation: The total cost is (2 + 1) = 3, and the number of moves is 2. Thus the final cost is (3 + 1) * (2 + 1) = 12.