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

Limits: 2 sec., 256 MiB

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

Input

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

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

Output

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

Constraints

$1 \le n \le 100$,

$1 \le a_i \le 10^9$.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 4 7 2 10 3	3

Notes

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