Improve the Permutation

Sergey thinks that some permutations are better than other permutations. He thinks that the permutations with the smaller number of inversions are nicer than the ones with the bigger number of inversions. So the smaller the number of inversions is, the nicer is the permutation. Sergey has a permutation A which he wants to make as nice as possible. This is kind of special permutation, because ini