What happens if you cast an ogre curse on a stick of RAM? It turns out that it can circlularly move arbitrary sequences of data in an efficient manner, but only at night. Find the minimum cost (and a valid sequence of moves) needed to sort a permutation of length . All elements of the permutation are indexed from 1 to .
The only permitted type of move allows you to take an element from some position and insert it at another position , shifting all elements in between by one. The cost of such a move is .
Formally, a move takes an element valued from position , "freeing" the index . We then shift the remaining elements in , such that the "free" position becomes . We then put in the free position at index .
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 first line contains an integer — the length of the permutation.
The second line contains integers v_1, v_2, \ldots, v_n — the values of the permutation.
1 \leq n \leq 3 \cdot 10^5,
1 \leq v_i \leq n,
v_i \neq v_j for all 1 \leq i < j \leq n.
On the first line, print two numbers and len\_moves — the minimum 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 x_k, y_k each, signifying that the -th operation should move the element from position x_k to position y_k (1 \leq k \leq len\_moves, 1 \le x_k, y_k \le n).
If several possible sequences of moves exist, you can print any of them. Note that you don’t need to minimize the number of moves, only the total cost. It’s guaranteed that there always exist a sequence of moves to sort a permutation.
Example
Example 1
Example 2
For the first example, the only move effectively swaps the elements on positions and .
For the second example, the permutation resulting after the first move is [2, 3, 4, 1, 5].
For the third example, the permutation is already sorted, so the optimal cost is zero, and no moves are needed.