Возрастающая подпоследовательность

Дан ряд из $n$ чисел. Из него можно вычеркнуть любые элементы, не меняя порядок оставшихся.

Какой наибольшей длины строго возрастающую последовательность можно так получить?

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

Одно число.

Состояние — «длина самой длинной возрастающей последовательности, заканчивающейся на элементе $i$». Переход перебирает предыдущий элемент такой последовательности. Ответ — наибольшее состояние.