Пусть у Вас имеется последовательность

. Определим

следующим образом.
Рассмотрим все возможные неубывающие подпоследовательности длины

вида

. И положим

- минимальный из

по всем таким подпоследовательностям (если, разумеется, таковые найдутся).
В частности,

- наименьший элемент в последовательности,

-наименьший из таких

, что

и т.д.
Докажите, что

Пусть теперь к этой последовательности добавили еще один элемент

. Бинарным поиском находим

Докажите, что для "новой" последовательности из

элементов изменится лишь

, которое надо будет изменить следующим образом:

.
(Есть еще 2 случая, когда новый элемент либо больше всех, либо меньше всех, но и там понятно что делать).