Ящик Пандоры

Будем считать динамику $$$dp_i$$$ — минимальное число действий, чтобы сделать неубывающим суффикс массива от $$$i$$$ до $$$n - 1$$$ (здесь и далее нумерация массивов с $$$0$$$ до $$$n - 1$$$).

Пусть $$$T(l, r) = 0$$$, если элементы с $$$l$$$ по $$$r$$$ одинаковые и $$$1$$$ иначе. Пойдем с конца массива и заметим, что

$$$dp_i$$$ = $$$dp_j$$$ + $$$T(i, j - 1)$$$, если $$$a_{j-1} = a_i$$$ и $$$j > i$$$.
Очевидно, для получения минимального количества действий, $$$dp_j + T(i, j - 1)$$$ должно быть минимально возможным. Заметим, что $$$dp_j + T(i, j - 1)$$$ минимально при минимальном $$$dp_j$$$, а если таких несколько, то при минимальном $$$j$$$.

Тогда для каждого числа $$$a_i$$$ из входных данных будем поддерживать $$$p[a_i]$$$ — индекс минимального $$$dp_j$$$, такого, что $$$a_{j-1} = a_i$$$ и $$$a_{j-1} < a_j$$$. Это можно поддерживать, проходя с конца по исходному массиву в процессе подсчета динамики.

Для того, чтобы не добавлять в $$$dp_i$$$ действие, когда мы хотим выравнять отрезок с $$$i$$$ по $$$j$$$, но на нем элементы и так одинаковые, заведем массив $$$c$$$, при этом $$$c_i = 1$$$, если $$$a_i = a_{i+1}$$$, иначе $$$0$$$. Теперь заведём массив $$$sum$$$, для которого $$$sum_i$$$ — сумма чисел в массиве $$$c$$$ на отрезке с $$$0$$$ по $$$i$$$ (массив префиксных сумм).

Теперь $$$q = sum[p[a[i]] - 1] - sum[i - 1]$$$ — количество чисел, равных $$$a_i$$$, на оптимальном отрезке, начинающемся с $$$i$$$. Тогда, если $$$q$$$ — не равно длине этого отрезка, значит на нем существует отличное от концов отрезка число, и нужно потратить действие для уравнивания и $$$dp_i = dp[p[a[i]] + 1$$$, иначе $$$dp_i = dp[p[a[i]]$$$.