Rezolvare PBinfo #1876

Cerința

Vlad și Alex sunt doi prieteni foarte buni. Aceștia sunt pasionați de jocuri și vor să vă propună unul: Se dau n numere naturale sub forma unui șir. Un subșir se numește “corect” dacă este ordonat crescător. Pentru a câștiga, jucătorul trebuie să ghicească lungimea maxima a unui astfel de subșir. Deoarece nu le place sa piardă, cei doi vă cer ajutorul.

Date de intrare

Fișierul de intrare sclm2.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire sclm2.out va conține pe prima linie numărul l, lungimea maximă a unui subșir “corect”.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000

Exemplu:

sclm2.in

7
3 1 4 3 5 6 9

sclm2.out

5

Explicație

Subșirul “corect” de lungime maxima este: 1 3 5 6 9 și are lungime 5.