Najdłuższy podciąg rosnący

Limit czasu: 0.5s | Limit pamięci: 64MB

Napisz program, który znajduje długość najdłuższego podciągu rosnącego danego ciągu: $a_1, a_2, \ldots, a_n$.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę $n$. Drugi wiersz zawiera $n$ liczb $a_i$.

Wyjście

Pierwszy i jedyny wiersz wyjścia zawiara długość najdłuższego podciągu rosnącego.

Ograniczenia

• $1 \le q \le 2\cdot 10^5$
• $1 \le a_i \le 10^9$

Przykłady

Wejście 1

8
7 3 5 3 6 2 9 8

Wyjście 1

4