Сортировка вагонов

Предположим, мы убрали из массива те элементы, что будем переставлять. Что останется? Останется последовательность подряд идущих чисел: a, a+1, …, b. Длина такой последовательности должна быть максимальна, чтобы минимизировать число элементов, которые надо переставлять.

Рассмотрим массив pos, где pos[p[i]] = i. Посмотрим на его подотрезок pos[a], pos[a+1], …, pos[b]. Эта последовательность должна возрастать, а ее длина, как уже сказали выше, должна быть наибольшей. Таким образом, надо выделить наибольший подотрезок в массиве pos, где значения pos[a], pos[a+1], …, pos[b] идут в возрастающем порядке.