Арена: сколько уровней подряд

В игре есть «Арена улучшений»: чтобы открыть новый уровень награды, ты должен показать цепочку боёв, где каждый следующий бой дал *строго больше* очков, чем предыдущий в этой цепочке. Бои можно выбирать не подряд: главное — сохранить их порядок по времени.

Найди, какой максимальной длины цепочку можно собрать.

Формат ввода

Первая строка: целое число n — количество боёв. Вторая строка: n целых чисел a1, a2, ..., an — очки за каждый бой по времени.

Формат вывода

Выведи одно целое число — максимальную длину строго возрастающей подпоследовательности.

Ограничения

• 1 ≤ n ≤ 20000
• -1000000 ≤ ai ≤ 1000000
• Как на олимпиадах, числа могут не помещаться в 32-битный тип (используй 64-битную арифметику; в Python это не проблема).

Пример

Ввод:

8
5 1 6 2 3 4 0 7

Вывод:

5

Пояснение: можно взять бои с очками 1 2 3 4 7 (они идут в правильном порядке и строго растут).

Ключевое наблюдение: нам важна не сама цепочка, а её длина. Если для какой-то длины мы умеем хранить *наименьший возможный последний элемент* ("хвост"), то это всегда выгодно: меньший хвост легче продолжить дальше.

Заведём массив d: d[k] — минимальный хвост строго возрастающей подпоследовательности длины k+1 среди уже просмотренных боёв. Тогда d всегда отсортирован по возрастанию, и для нового значения x можно быстро найти, какую длину он улучшает.

Почему работает: если x может стать хвостом для длины k+1, то лучше хранить минимальный хвост — он оставляет максимум шансов достроить цепочку.

План:

• Идём слева направо по очкам a.
• Для текущего x находим первую позицию pos, где d[pos] >= x (это lower_bound).
• Если такой позиции нет — дописываем x в конец d (нашли более длинную цепочку).
• Иначе заменяем d[pos] = x (улучшаем хвост для этой длины).
• Ответ — len(d).

Мини-сниппет для шага поиска/обновления:

• pos = lower_bound(d, x) # первая d[pos] >= x
• d[pos] = x или d.append(x) если pos == len(d).

Сложность: n шагов, каждый с бинарным поиском по d → O(n log n), память O(n).

Частая ошибка: перепутать строгость. Для *строго* возрастающей подпоследовательности нужен именно поиск первой >= x. Если взять первую > x, получится вариант для неубывающей последовательности и ответ может стать неверным при равных значениях.