==Include(page="template/taskheader" task_id="subsiruri")==
 
==Include(page="template/raw")==
 
Subsiruri
 
 
 
Se considera un sir de n numere intregi distincte x[1], x[2], ..., x[n].
 
h2. Cerinta
 
Sa se determine lungimea subsirurilor x[i1], x[i2], ..., x[ik] de lungime maxima, unde i[1] < i[2] < ... < i[k] si x[i1] < x[i2] < ... < x[ik], precum si numarul lor.
 
h2. Date de Intrare
 
. Pe prima linie a fisierului subsiruri.in se afla numarul natural n, reprezentand lungimea sirului.
 
. Pe urmatoarele n linii se afla cate un numar intreg.
 
h2. Date de Iesire
 
. Pe prima linie a fisierului de iesire subsiruri.out se va scrie numarul natural lungmax, reprezentand lungimea maxima a subsirurilor crescatoare.
 
. Pe urmatoarea linie se va scrie numarul subsirurilor de lungime lungmax. Acest numar se va afisa modulo 9901.
 
h2. Restrictii si precizari
 
. 5 -L- n -L- 1000;
 
. -32000 -L- x[k] -L- 32000;
 
h2. Exemplu
 
subsiruri.in subsiruri.out Explicatie
 
10 4 Sunt 6 subsiruri crescatoare de lungime maxima 4:
 
1 6 1 3 8 9
 
-12 1 3 7 9
 
3 -12 3 8 9
 
8 -12 3 7 9
 
-25 -12 0 7 9
 
0 -25 0 7 9
 
7
 
-18
 
9

==Include(page="template/taskheader" task_id="subsiruri")==
 
Se considera un sir de $N$ numere intregi distincte {$x{~1~}$}, {$x{~2~}$}, ..., {$x{~N~}$}.
 
h2. Cerinta
 
Sa se determine lungimea subsirurilor {$x{~i{~1~}~}$}, {$x{~i{~2~}~}$}, ..., {$x{~i{~k~}~}$} de lungime maxima, unde {$i{~1~} < i{~2~} < ... < i{~k~}$} si {$x{~i{~1~}~} < x{~i{~2~}~} < ... < x{~i{~k~}~}$}, precum si numarul lor.
 
h2. Date de intrare
 
Pe prima linie a fisierului $subsiruri.in$ se afla numarul natural $N$, reprezentand lungimea sirului. Pe urmatoarele $N$ linii se afla cate un numar intreg.
 
h2. Date de iesire
 
Pe prima linie a fisierului $subsiruri.out$ se va scrie numarul natural $lungmax$, reprezentand lungimea maxima a subsirurilor crescatoare. Pe urmatoarea linie se va scrie numarul subsirurilor de lungime $lungmax$. Acest numar se va afisa modulo $9901$.
 
h2. Restrictii si precizari
 
* $5 &le; n &le; 1 000$
* $-32 000 &le; x{~k~} &le; 32 000$
 
h2. Exemplu
 
table(example). |_. subsiruri.in|_. subsiruri.out|
|10
1
-12
3
8
-25
0
7
-18
9
2
|4
6
|
 
h3. Explicatii
 
Sunt 6 subsiruri crescatoare de lungime maxima 4:
$1 3 8 9$
$1 3 7 9$
$-12 3 8 9$
$-12 3 7 9$
$-12 0 7 9$
$-25 0 7 9$
 
 
 
==Include(page="template/taskfooter" task_id="subsiruri")==

2
==Include(page="template/taskfooter" task_id="subsiruri")==

969