CSES - Alijono
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Annettuna on taulukko, jossa on nn 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 nn: taulukon koko.

Sitten syötteessä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n: taulukon sisältö.

Tuloste

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

Rajat

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

Esimerkki

Syöte:

8
7 3 5 3 6 2 9 8

Tuloste:

4