Починка массива

Заметим пару полезных фактов: если с помощью операций перенести $$$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\}$$$, то есть разобьется на отрезки из соседних чисел. Иначе массив не будет отсортирован. Тогда заметим:

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

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

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