Annettuna on taulukko, jossa on n lukua. Tehtäväsi on etsiä pisin nouseva alijono taulukossa.

Nouseva alijono tarkoittaa joukkoa taulukon lukuja, jotka ovat samassa järjestyksessä kuin taulukossa ja seuraava luku on suurempi kuin edellinen luku.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: taulukon koko.

Sitten syötteessä on n kokonaislukua x_1,x_2,\ldots,x_n: taulukon sisältö.

Tuloste

Ohjelmasi tulee tulostaa, kuinka pitkä on pisin nouseva alijono.

Rajat

• 1 \le n \le 10^5
• 1 \le x_i \le 10^9

Esimerkki

Syöte:

8
7 3 5 3 6 2 9 8

Tuloste:

4