Возрастающая, но быстро

Та же задача о наибольшей строго возрастающей подпоследовательности, но чисел до двухсот тысяч.

Перебор всех пар не успеет.

В первой строке число $n$ от $1$ до $2 \cdot 10^5$. Во второй — $n$ чисел от $-10^9$ до $10^9$.

Одно число.

Держите список: на месте $L$ — наименьшее число, которым может заканчиваться возрастающая последовательность длины $L + 1$. Этот список всегда возрастает, поэтому место для очередного числа ищется двоичным поиском. Длина списка и есть ответ. Обратите внимание: сам список — не ответ на вопрос «какая именно последовательность», он лишь хранит хвосты.