Что написано в условии? Сказано, что мы можем взять левую башню и обрезать правую башню высотой первой, приечм мы можем это делать только с самой ближайшей справа башней, которая больше левой. А можно ли любую башню справа обрезать, а не только самую ближайшую.

Можно. Мы можем много раз подряд выбирать башню $$$i$$$, тогда с ее помощью можно обрезать все башни правее нее. Тогда какую минимальную высоту можно получить в башне $$$i$$$?

В башне $$$i$$$ мы можем получить высоту $$$\min(a_1,a_2,\ldots,a_i)$$$, но никак не меньше. Тогда чему равен ответ?

Пусть $$$A_i$$$ — префиксный минимум, тогда ответ $$$\sum_i A_i$$$

Что происходит в задаче? Мы сначала перемешиваем массив $$$b$$$, а потом пытаемся превратить его в $$$a$$$ с помощью добавления неотрицательных чисел. Тогда какой критерий можно сформулировать для массива $$$b$$$ после перемешивание, что его можно превратить в $$$a$$$?

Массив $$$b$$$ можно превратить в $$$a$$$ тогда и только тогда, когда $$$b_i \le a_i$$$ для всех $$$i$$$. Тогда посмотрим на исходный массив $$$b$$$, посмотрим на какой-то элемент $$$b_i$$$, на каких позициях он может стоят в финальном ответе?

Найдем для него минимальный $$$j$$$, что $$$b_i \le a_j$$$, тогда мы можем положить $$$b_i$$$ в любую позицию, начиная с $$$j$$$, то есть $$$(j,j+1,\ldots)$$$. Тогда какую простую стратегию можем придумать?

Можем идти слева направо и если встретили $$$b_i \gt a_i$$$, тогда для него можем найти миниальную позицию $$$j$$$, что $$$b_i \le a_j$$$ и подвинуть этот элемент туда. Ограничения позволяют решить задачу за $$$O(n^2)$$$. Почему это работает?

Во-первых, мы обязаны подвинуть элемент $$$b_i$$$ хотя бы в $$$j$$$, но с другой стороны не имеет смысл сейчас его двигать дальше, потому что мы сможем это сделать на следующих шагах, если потребуется.

В большинстве задач, можно попробовать решать их, идя слева направо, то есть попытаться решить задачу для префикса $$$a_1,a_2,\ldots,a_i$$$. В этой задаче стоит сделать именно так, потому что в итоге мы хотим получить отсортированный массив, значит максимум будут всегда справа. Как это сделать?

Пускай мы решили задачу для префикса $$$a_1,\ldots,a_{i-1}$$$. Мы хотим добавить $$$a_i$$$. Какие бывают случаи?

Если $$$a_{i-1} \le a_i$$$, то префикс уже отсортирован, а если $$$a_i \lt a_{i-1}$$$?

Тогда мы обязаны свапать $$$a_i$$$ с предыдущим элементом пока префикс не отсортирован. Что тогда будет происходить?

Тогда сам элемент $$$a_i$$$ не поменяется, но подвинется куда-то влево, а те элементы, с которыми мы поменяемся местами увеличиться на $$$a_i$$$. Отлично, научились решать задачу за $$$O(n^2)$$$, но можно ли быстрее? Нужно ли нам знать весь префикс?

Так как в итоге нам нужно узнать только последний элемент, то можем помнить только его, тогда если $$$a_{i-1} \le a_i$$$, то новый макс. элемент равен $$$a_i$$$, а иначе $$$a_{i-1}+a_i \ge a_{i-1}$$$.

Какое самое простое условие должно выполняться, чтобы строка была красивой? В каких случаях мы точно не сможем сделать ни одной операции?

Строка точно не является красивой, если она содержит хотя бы два элемента, причем все элементы чередуются (например $$$01010101$$$), то есть нет одинаковых соседей.

Задача похожа на часто-встречающуюся задачу, когда два соседних элемента заменяют на их сумму. В такой задаче сумма массива никогда не меняется. Можно ли сделать в этой задаче что-то похожее?

Пусть $$$a$$$ — это число, на которое мы заменим нули, а $$$b$$$ — число, на которое мы заменим единицы. Тогда мы хотим, чтобы $$$a + a = b, b + b = a$$$, то есть $$$2a=b,2b=a$$$. Что тогда?

Тогда $$$a = 2\cdot b = 2\cdot (2\cdot a) = 4a$$$, то есть $$$3a = 0$$$. На что похоже?

Это похоже на арифметику по модулю $$$3$$$. Возьмем $$$a \equiv +1\pmod{3}, b \equiv -1 \pmod{3}$$$