== include(page="template/taskheader" task_id="secvente2") ==
Poveste şi cerinţă...
Considerăm şirul de numere naturale nenule distincte $a{~1~}$, $a{~2~}$, ..., $a{~N~}$. Notăm cu $L{~i~}$ lungimea maximă a unei secvenţe de elemente cu valori consecutive care se poate obţine prin ordonarea crescătoare a primelor $i$ elemente din şirul dat. De exemplu, pentru şirul $7, 2, 3, 8, 20, 4, 10, 9$ avem: $L{~1~} = 1$, $L{~2~} = 1$, $L{~3~} = 2$, $L{~4~} = 2$, $L{~5~} = 2$, $L{~6~} = 3$, $L{~7~} = 3$, $L{~8~} = 4$.
h2. Cerinţă
Să se determine $L{~1~}$, $L{~2~}$, ..., $L{~N~}$.
h2. Date de intrare
Fişierul de intrare $secvente2.in$ ...
Fişierul de intrare $secvente2.in$ conţine pe prima linie numărul natural $N$. Pe fiecare din următoarele $N$ linii se găseşte câte un număr natural, deci pe linia $i+1$ se va afla elementul $a{~i~}$, pentru $i=1...N$.
h2. Date de ieşire
În fişierul de ieşire $secvente2.out$ ...
În fişierul de ieşire $secvente2.out$ conţine exact $N$ linii. Pe linia $i$ ({$i = 1...N$}) se va afişa valoarea $L{~i~}$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ N ≤ 200 000$
* $1 ≤ a{~i~} ≤ 1 000 000$, pentru orice $i = 1...N$
* Pentru $35%$ din teste se garantează că $N ≤ 1000$
h2. Exemplu
table(example). |_. secvente2.in |_. secvente2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 8
7
3
2
8
20
4
10
9
| 1
1
2
2
2
3
3
4
|
h3. Explicaţie
...
$L{~1~}$. Şirul: $7$. Lungime maximă $1$
$L{~2~}$. Şirul: $7,3$. Lungime maximă $1$
$L{~3~}$. Şirul: $7,3,2$. Şirul sortat este $2,3,7$. Lungimea maximă este $2$ (dată de secvenţa $2,3$)
$L{~4~}$. Şirul: $7,3,2,8$. Lungime maximă $2$ (dată de $2,3$)
$L{~5~}$. Şirul: $7,3,2,8,20$. Lungime maximă $2$ (dată de $2,3$).
$L{~6~}$. Şirul: $7,3,2,8,20,4$. Şirul sortat este $2,3,4,7,8,20$. Lungimea maximă este $3$ (dată de secvenţa $2,3,4$).
$L{~7~}$. Şirul: $7,3,2,8,20,4,10$. Lungime maximă $3$ (dată de $2,3,4$).
$L{~8~}$. Şirul: $7,3,2,8,20,4,10,9$. Şirul sortat este $2,3,4,7,8,9,10,20$. Lungimea maximă este $4$ (dată de secvenţa $7,8,9,10$).
== include(page="template/taskfooter" task_id="secvente2") ==
== include(page="template/taskfooter" task_id="secvente2") ==
