Ilgiausias didėjantis posekis

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_jk, 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 <= 1000). 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