Important observations

When looking at the description of what happens when moving a player, we can see that if we move a player towards the front of the list, the moving cost of some other players increases, whereas if we move a player towards the end of the list, the moving cost of some other players decreases. So, it might be helpful to move players first which have to be moved towards the end of the list to decrease the moving costs of future moves. This observation may lead to the following two ideas:

1. Each player is moved at most once.
2. The players who are moved are moved in ascending order according to their score.

A proof that these two ideas are correct will follow later.

Brute force solution

Using the two ideas mentioned above, a brute force solution would try all selections of players to be moved, and then move them to their required position in ascending order according to their score. The complexity of this solution would be ~\mathcal O(n^2 \cdot 2^n)~.

Dynamic programming solution

Let the players be numbered from ~1~ to ~n~ according to their final position in the ranklist. With dynamic programming, we want to determine the minimum cost to get the players ~i \dots n~ in their correct relative order with the first of these players at original position ~j~. It is tricky to determine the current position of the next player to be moved. It would be far easier if we knew that all players ~(i+1) \dots n~ already moved towards the end of the list; in that case, in order to determine the current position of player ~i~, we could count how many players with bigger scores exist which have an original index position smaller than player ~i~. Obviously, if some of the players with the ~n-i~ smallest scores didn't move, the current position for player ~i~ determined by this method can be too small.

However, if we assign a moving cost to each player who doesn't move, we can take care of the underestimated moving cost for players with bigger score. Let's see what happens if we didn't move player ~j~. This means that players with bigger score will be moved before him, so when determining the position of a player ~i~ which appears after player ~j~ in the list, the determined rank would be too small by ~j-i~. So the moving cost for a player who doesn't move is the sum of ~j-p_i~ for all players ~p_i < j~ which appear between player ~j~ and the position of player ~j+1~.

It is possible to implement a dynamic programming solution using this idea with complexity ~\mathcal O(n^2)~. With dynamic programming, we can determine the minimal overall moving costs and which players were moved. Now, we simply need the second part of the brute force solution to generate the actual moves performed.

Proof

Here is the proof of why the two ideas mentioned above are correct:

Let's look at the player ~p_\min~ with the smallest score, who has to end up at position ~n~.

Claim 1: If ~p_\min~ is moved at all, it is optimal to move him directly to the end of the list.

Proof: Obviously, moving him towards the front will only increase the costs of other players to be moved. So assume he will be moved towards the end to a position ~i < n~ (thus saving ~n-i~ steps). Now there are two possibilities: either, the ~n-i~ players after him in the list have to be moved and their costs are increased by ~1~ (as opposed to that ~p_\min~ was moved to the end), or ~p_\min~ has to be moved again, which clearly is not optimal.

Claim 2: If ~p_\min~ is moved at all, we can do this in the first move.

Proof: Following from Claim 1, we already know the second part of the moving costs is fixed. So the only reason not to move ~p_\min~ first is that his current position decreases caused by moving other players. But these players have their moving costs increased by ~1~ because ~p_\min~ wasn't moved to the end.

If ~p_\min~ is moved, we have reduced our problem to the same problem with ~n-1~ players. If ~p_\min~ is not moved, we have a similar problem with ~n-1~ players with the additional restriction that all players after ~p_\min~ have to be moved before ~p_\min~.

Let ~p'_\min~ be the player with the smallest score among the remaining ~n-1~ players. We can see that it does not help to move ~p'_\min~ after ~p_\min~, because that would mean we have to move him again, and we gain nothing from moving him past other players still to be moved (for each of them, we decreased the moving cost by ~1~, and increased the moving cost of ~p'_\min~ by at least one). If ~p'_\min~ is currently placed before ~p_\min~ in the list, by similar arguments as for Claim 1 we can argue that if ~p'_\min~ is moved at all, it is optimal to move him directly before ~p_\min~. Also, Claim 2 still works. So we are left with the case that ~p'_\min~ is currently placed after ~p_\min~ and has to be moved towards the front. If there are players between ~p_\min~ and ~p'_\min~, we could consider moving them first. If we move ~p'_\min~ first, the start positions of the players in between are increased by ~1~. But if we move some player in between first, the end position where ~p'_\min~ has to be moved to increases by ~1~, so it can't be bad if we move ~p'_\min~ first.

So, we can see that by using induction and the arguments presented above we can prove that each player is moved at most once, and the players can be moved in ascending order according to their score.