Максимальная неубывающая подпоследовательность за n*logn

[BanmaN]

Здравствуйте.

Подскажите, пожалуйста, алготим нахождения максимальной неубывающей подпоследовательности за время $n \cdot lg n$.

[sup]

Пусть у Вас имеется последовательность $a_1,a_2 \dots a_n$. Определим $A_k$ следующим образом.
Рассмотрим все возможные неубывающие подпоследовательности длины $k$ вида $a_{i_1},a_{i_2} \dots a_{i_k}$. И положим $A_k$ - минимальный из $a_{i_k}$ по всем таким подпоследовательностям (если, разумеется, таковые найдутся).
В частности, $A_1$ - наименьший элемент в последовательности, $A_2$ -наименьший из таких $a_i$, что $\exists j<i,a_i \geqslant a_j$ и т.д.
Докажите, что $A_1 \leqslant A_2 \leqslant A_3 \leqslant \cdots$
Пусть теперь к этой последовательности добавили еще один элемент $a_{n+1}$. Бинарным поиском находим
$A_k \leqslant a_{n+1} < A_{k+1}$
Докажите, что для "новой" последовательности из $n+1$ элементов изменится лишь $A_{k+1}$, которое надо будет изменить следующим образом: $A_{k+1}=a_{n+1}$.
(Есть еще 2 случая, когда новый элемент либо больше всех, либо меньше всех, но и там понятно что делать).