First, find the largest suffix of the permutation that is in increasing order. For example for the array 3 6 5 1 2 4 7, the largest such suffix will be 1 2 4 7. Then we need to place only the elements 3 6 5 at their correct positions and the array will be sorted after that. For calculating the cost of shifting the element from 3 6 5, we can find the number of jumps we need to make in the sorted suffix plus the number of elements that are remaining in the 3 6 5 part. Say we placed 3 at its correct position. Now the cost will be 2 + 2, 2 moves for going beyond 6 5 and 2 again for going beyond 1 2. To calculate the latter we can use lower_bound on 1 2 4 7. Now we want to place 6 in the correct position. To calculate moves we can either modify our suffix 1 2 4 7, i.e. insert 3 in it and then repeat the same procedure or we can just add the number of elements before 6 which are less than 6 in the part 3 6 5, which can be done efficiently using Fenwick Tree or Segment Tree.
If you find any counter test then please inform.