Найбільша зростаюча підпослідовність

Обмеження: 2 сек., 256 МіБ

Вам задано послідовність із \(n\) цілих чисел \(a_i\). Ваша задача — знайти довжину найбільшої зростаючої підпослідовності заданої послідовності.

Вхідні дані

У першому рядку задано ціле число \(n\).

У наступному рядку задано \(n\) цілих чисел — послідовність \(a_i\).

Вихідні дані

Виведіть довжину найбільшої зростаючої підпослідовності.

Обмеження

\(1 \le n \le 100\),

\(1 \le a_i \le 10^9\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 4 7 2 10 3	3

Примітки

У прикладі найбільшою зростаючою підпослідовністю є [4, 7, 10].