Минимизация обменами

Пытаемся на первую позицию поставить 1, если успели — сделаем это. Иначе пытаемся на первую позицию поставить 2, если успели — сделаем это. И т.д. до 9. Потом со второй позицией и цифрой на ней. Если использовать дерево Фенвика или дерево отрезков для подсчета числа использованных цифр на отрезке, то асимптотика будет $$$O(n \cdot ln{n})$$$.