Вот наблюдение, которое, я думаю, можно превратить в решение O (n log n). Предположим, у вас есть ответ для последних k элементов массива. Что вам нужно для того, чтобы определить значение элемента непосредственно перед этим? Вы можете думать о последних k элементах как о разделенных на серию диапазонов, каждый из которых начинается с некоторого элемента и продолжается до тех пор, пока не достигнет меньшего элемента. Эти диапазоны должны быть в порядке убывания, поэтому вы можете подумать о том, чтобы выполнить бинарный поиск по ним, чтобы найти первый интервал, меньший, чем этот элемент. Затем вы можете обновить диапазоны, чтобы учесть этот новый элемент.
Теперь, как лучше это представить? Лучший способ, о котором я подумал, - это использовать Splay Tree, ключи которого - это элементы, определяющие эти диапазоны, а значения - это индекс, с которого они начинаются. Затем вы можете за время O (log n) амортизировать выполнить поиск предшественника, чтобы найти предшественника текущего элемента. Это находит самое раннее значение меньше текущего. Затем за время амортизации O (log n) вставьте текущий элемент в дерево. Это представляет собой определение нового диапазона от этого элемента вперед. Чтобы отбросить все диапазоны этого супердея, вы затем вырезаете правый дочерний элемент нового узла, который, поскольку это дерево сопряжения находится в корне, из дерева.
В целом, это делает O (n) итераций процесса O (log n) для всего O (n lg n).