== include(page="template/taskheader" task_id="consir") ==
Poveste si cerinta...
Vultur a gasit in cartea de chimie o problema pe care nu stie sa o rezolve si are nevoie de ajutorul vostru. Se da o secventa $A$, formata din $N$ numere naturale. Un consir este un sir de numere naturale $i{~1~}, i{~2~} ... i{~p~}$ (cu valori cuprinse intre $1$ si $N$) cu proprietatea ca $A[i{~1~}], A[i{~2~}] ... A[i{~p~}]$ sunt numere consecutive. Mai exact $A[i{~2~}]=A[i{~1~}]+1$, $A[i{~3~}]=A[i{~2~}]+1$ ... $A[i{~p~}]=A[i{~p-1~}]+1$. Determinati $K$, lungimea maxima a unui consir ce se poate forma, precum si numarul de consiruri distincte de lungime $1$, $2$ ... $K$.
h2. Date de intrare
...
Pe prima linie a fisierului $consir.in$ se va afla numarul $N$ avand semnificatia din enunt. Pe urmatoarele $N$ linii se afla valorile secventei $A$, mai exact pe linia $i+1$ se afla valoarea lui $A[i]$.
h2. Date de iesire
...
Pe prima linie a fisierului $consir.out$ se va afla valoarea $K$, avand semnificatia din enunt. In continuare vor urma $K$ linii, pe linia $i+1$ aflandu-se numarul de consiruri distincte de lungime $i$.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 310 000$
* Termenii sirului au valori cuprinse intre $1$ si $1 000 000$
* Se garanteaza ca fiecare raspuns are o valoare mai mica decat $2^63^$ (se incadreaza pe tipuri de date intregi pe 64 biti fara semn)
* Lungimea unui consir este data de numarul de elemente
* Doua consiruri $X$ si $Y$ sunt distincte daca exista o pozitie $i$ astfel incat $X{~i~}$ diferit de $Y{~i~}$
* In cel putin 30% din teste $N ≤ 1000$
h2. Exemplu
table(example). |_. consir.in |_. consir.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
1
2
1
3
4
5
| 5
6
5
4
3
2
|
h3. Explicatie
...
Cele 2 consiruri de lungime 5 sunt $1 2 4 5 6$ si $3 2 4 5 6$
Cele 3 consiruri de lungime 4: $1 2 4 5$, $3 2 4 5$ si $2 4 5 6$
Cele 4 consiruri de lungime 3: $1 2 4$, $2 4 5$, $3 2 4$ si $4 5 6$
Cele 5 consiruri de lungime 2: $1 2$, $2 4$, $4 5$, $3 2$ si $5 6$
Cele 6 consiruri de lungime 1: $1$, $2$, $3$, $4$, $5$ si $6$
== include(page="template/taskfooter" task_id="consir") ==
