Вот теперь он точно закончился.

В задаче А легко за O(N) найти для какого-то момента t, какая будет разница между максимальной и минимальной высотой. Посчитаем эту величину для всех "интересных" моментов и выберем минимум.

Интересными будем считать моменты, когда что-нибудь меняется, а именно тип движения или относительный порядок высот. Поэтому интересны следующие:

1) t=0

2) момент приземления i-того.

3) момент, когда i и j-тый оказываются на одной высоте

4) момент, когда i-тый пролетает высоту, на которой был j-тый

5) момент, когда i-тый занимает максимальную высоту

Их O(N^2), поэтому время работы O(N^3)

Алгоритмом манакера найдем самый большой палиндром для каждого центра, затем для каждой правой сумма левых считается прибавлением арифметических прогрессий на отрезке.

Конечно! Для каждой позиции $$$j$$$ посчитаем сумму всех индексов $$$k\geqslant j$$$, для которых подстрока между ними включительно -- палиндром. То же самое сделаем для каждой позиции влево, после этого надо будет просто найти $$$\sum_{j=1}^{n-1}{dpr}_{j+1}{dpl}_j$$$. Как посчитать эти динамики:

Заведём два дерева отрезков на линейных функциях (одно для динамики вправо и одно влево). Посчитаем манакером для каждого центра наибольший палиндром. Для каждого палиндрома прибавим в первом дереве линейную функцию от левого края до центра, во втором -- от центра до правого края. Линейная функция такова, что по индексу возвращает индекс симметричной позиции (то есть отражает относительно центра). Понятно, почему это даст то, что надо.