Сама подпоследовательность

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

Если таких несколько, подойдёт любая.

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

Элементы подпоследовательности через пробел.

Кроме длины запоминайте, за каким элементом продолжилась последовательность. Потом идите от лучшего состояния назад, как при восстановлении пути.