Minimization by Swaps

We try to place 1 in the first position; if we succeed, we do it. Otherwise, we try to place 2 in the first position; if we succeed, we do it. And so on up to 9. Then we move to the second position and the digit at that position. If we use a Fenwick tree or a segment tree to count the number of used digits in the segment, the asymptotic complexity will be $$$O(n \cdot \ln{n})$$$.