Ilgiausias didėjantis posekis (2)

Pradinių duomenų failas:

posekis.in  

Rezultatų failas:

posekis.out  

Laiko apribojimas:

2 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Čia – indeksas. O čia – indekso indeksas.
Vienas dėstytojas

Sekos \(a_{1}\), \(a_{2}\), …, \(a_{n}\) posekiu vadinama seka \(a_{j_{1}}\), \(a_{j_{2}}\), …, \(a_{j_{k}}\), kur 1 <= \(j_{1}\) < \(j_{2}\) < … < \(j_{k}\) <= n.

Seka \(a_{1}\), \(a_{2}\), …, \(a_{n}\) vadinama didėjančia, jei \(a_{1}\) < \(a_{2}\) < … < \(a_{n}\).

Parašykite programą, kuri rastų ilgiausio duotosios sekos didėjančio posekio ilgį.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas skaičius n (1 <= n <= 1000000). Antroje eilutėje įrašyti sekos nariai \(a_{1}\), \(a_{2}\), …, \(a_{n}\), atskirti tarpais (1 <= \(a_{i}\) <= 1 000 000 000).

Rezultatai

Į rezultatų failą turi būti įrašytas vienas skaičius – ilgiausio duotosios sekos didėjančio posekio ilgis.

Pavyzdys

4
2 6 1 3

2

11
6 3 12 10 4 11 6 1 8 12 7

5