Laiko ribojimas: 2s

Atminties ribojimas: 16MB

Duomenų failas: posekis2.in

Rezultatų failas: posekis2.out

Jei norite pateikti savo sprendimą - prisijunkite.

Ilgiausias didejantis posekis 2

Sekos a_1,a_2,...,a_n posekiu vadinama seka a_{j1},a_{j2},...,a_{jk}, kur 1\\lej_1<j_2<...<j_k\\len.

Seka a_1,a_2,...,a_n vadinama didejancia, jei a_1<a_2<...<a_n.

Parašykite programa, kuri rastu ilgiausio duotosios sekos didejancio posekio ilgi.

Pradiniai duomenys

Pirmoje pradiniu duomenu failo eiluteje irašytas skaicius n (1\\len\\le1000000). Antroje eiluteje irašyti sekos nariai a_1,a_2,...,a_n, atskirti tarpais (1\\lea_i\\le1000000000).

Rezultatai

I rezultatu faila turi buti irašytas vienas skaicius - ilgiausio duotosios sekos didejancio posekio ilgis.

Pavyzdys

Pradiniai duomenys Rezultatai Paaiškinimas
4
2 6 1 3
2
Ilgiausi didejantys posekiai yra keli: (2, 6), (2, 3), (1, 3). Ilgesnio didejancio posekio nera.
11
6 3 12 10 4 11 6 1 8 12 7
5
Ilgiausias didejantis posekis šioje sekoje: 3 4 6 8 12.