Заметим пару полезных фактов: если с помощью операций перенести $$$k$$$ элементов в начало и $$$m$$$ элементов в конец массива, то:

• Можно выполнять операции с такой очередностью, что перенесенные элементы будут в любом необходимом порядке, например отсортированном.
• Элементы, которые перенесены в начало являются $$$k$$$ наименьшими числами исходного массива, а в свою очередь элементы, перенесенные в конец должны быть $$$m$$$ наибольшими числами в массиве.

Таким образом, чтобы массив был отсортирован, все элементы, которые не переносились должны быть в отсортированном порядке относительно друг друга.

Для облегчения задачи выполним масштабирование: отсортируем первоначальные элементы в отдельном массиве, а затем уберем повторы. Затем в исходном массиве заменим элементы, на их индексы в полученном массиве. Например, если изначально массив выглядел, как $$$\{3, 1, 2, 3, 40, 55\}$$$, после масштабирования он будет выглядеть следующим образом: $$$\{2, 0, 1, 2, 3, 4\}$$$. Заметим, что так как масштабирование не влияет на порядок элементов, ответ на задачу для исходного массива и нового будет идентичным. Более того, теперь в массиве все значения не превосходят его длину.

После масштабирования выполняется следующее свойство, если в массиве есть элемент $$$x$$$, то в нем также есть элемент $$$x+1$$$, либо $$$x$$$ является наибольшим элементом массива. Тогда заметим, что после удаления из массива элементов, к которым была применена операция оставшиеся элементы будут образовывать последовательность следующего вида: $$$\{x, x, \dots, x, x + 1, x + 1 \dots x+1, \dots x + q\}$$$, то есть разобьется на отрезки из соседних чисел. Иначе массив не будет отсортирован. Тогда заметим:

• Если к хотя бы одному элементу со значением $$$x$$$ применяется операция по переносу в начало, то нигде среди оставшихся элементов кроме как в начале не могут находится элементы с таким же значением.
• Аналогичное верно для переносов в конец.

Для начала для каждого значения массива посчитаем его первое и последнее вхождение в исходный массив, составим из них отрезок $$$[l_x;r_x]$$$. Тогда оставшиеся элементы представляются, как последовательно соединенные отрезки, а также для каждого отрезка верно:

• Все значения за которые он отвечает были переставлены, тогда отрезок не входит в оставшиеся элементы.
• Все элементы из этого отрезка остались нетронутыми, тогда он входит в оставшиеся элементы.
• Некоторые (не все) элементы со значениями, за которые отвечал отрезок, могли быть перенесены вперед и тогда отрезок $$$[l_x, m_x]$$$ будет являться началом последовательности оставшихся элементов, где $$$m_x$$$ некоторое вхождение $$$x$$$.
• Аналогично для переносов в конец.

Некоторые отрезки вполне могут «не мешать друг другу», например, если рассмотреть некоторое значение $$$x$$$ и будет верно, что $$$r_x < l_{x+1}$$$, заменим эти два отрезка на отрезок $$$[l_x; r_{x+1}]$$$. После всех возможных замен получится, что последовательность оставшихся элементов выглядит следующим образом: Либо начало отрезка и конец следующего за ним, либо три подряд отрезка, у крайних из которых взяты только части. Все нужные значения $$$m_x$$$ необходимые для нахождения частей отрезков предлагается искать двоичным поиском.

Итоговая сложность решения O($$$n \log n$$$).