Разбор письменного экзамена ШАД. Задача 9. Индекс ближайшего превосходящего элемента

В этом году мы решили помочь тем, кто готовится к поступлению в Школу анализа данных, и поделиться решениями нескольких заданий из вариантов письменного экзамена, демонстрирующими полезные приёмы.

[Nakilon]

Могли бы проиллюстрировать это как дерево с одной активной веткой, которая либо удлиняется, либо обрезается и продолжает расти из нового места. Т.е на каждый элемент два раза log поиск запускаем -- для поиска места врезки и для поиска первого эл-нта, который в заданное кол-во раз больше.

[anton_khanaev]

почему синие столбцы будут отсортированы по возрастанию? они же только больше
a = [1, 2, 9, 5, 3, 7]
пусть i = 1, a[i] = 2
для него "синими" элементами будут 9, 5 и 7
Но они не отсортированы по возрастанию