== include(page="template/taskheader" task_id="salsa") ==
Recent, Bulănel a început să ia cursuri de salsa. Fiind un dansator desăvârşit, a învăţat rapid N figuri numerotate de la 1 la N pe care le poate folosi la petreceri. Pentru fiecare figură i, el ştie exact o figură, nextMove[i], cu care poate continua. Fiecare figură durează o secundă pentru a fi executată.
Recent, Bulănel a început să ia cursuri de salsa. Fiind un dansator desăvârşit, a învăţat rapid $N$ figuri numerotate de la $1$ la $N$ pe care le poate folosi la petreceri. Pentru fiecare figură $i$, el ştie exact o figură, $nextMove[i]$, cu care poate continua. Fiecare figură durează o secundă pentru a fi executată.
Melodiile de la petreceri au lungimi variate. Curios din fire, Bulănel se întreabă câteodată în câte moduri poate să danseze pe o melodie de X secunde. Pentru că nu vrea să plictisească fetele, pe parcursul melodiei Bulănel va trebui sa folosească doar figuri diferite. Acesta poate începe cu orice figură doreşte.
Melodiile de la petreceri au lungimi variate. Curios din fire, Bulănel se întreabă câteodată în câte moduri poate să danseze pe o melodie de $X$ secunde. Pentru că nu vrea să plictisească fetele, pe parcursul melodiei Bulănel va trebui sa folosească doar figuri diferite. Acesta poate începe cu orice figură doreşte.
Ajutaţi-l pe Bulănel să afle în câte moduri poate să danseze pe o melodie de i secunde pentru fiecare i între 1 şi N. Două moduri se consideră diferite dacă există un indice i, astfel încât figurile efectuate la secunda i în cele două moduri sunt diferite.
Ajutaţi-l pe Bulănel să afle în câte moduri poate să danseze pe o melodie de $i$ secunde pentru fiecare $i$ între $1$ şi $N$. Două moduri se consideră diferite dacă există un indice $i$, astfel încât figurile efectuate la secunda $i$ în cele două moduri sunt diferite.
h2. Date de intrare
Fişierul de intrare $salsa.in$ ...
Fişierul de intrare salsa.in conţine pe prima linie un număr întreg $N$, reprezentând numărul total de figuri. Următoarea linie conţine $N$ numere întregi, al $i$-lea dintre acestea reprezentând $nextMove[i]$, figura care se poate executa după figura $i$.
h2. Date de ieşire
În fişierul de ieşire $salsa.out$ ...
Fişierul de ieşire $salsa.out$ trebuie să conţină $N$ numere întregi, al $i$-lea dintre acestea reprezentând răspunsul pentru întrebarea $i$ - mai exact, în câte moduri poate Bulănel să danseze pe o melodie de $i$ secunde.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 100 000$
* Se garantează că $nextMove[i] ≠ i$ şi $1 ≤ nextMove[i] ≤ N$, pentru orice $i$ intre $1$ şi $N$.
* Pentru unele teste în valoare de $10$ puncte, se garantează că şirul $nextMove[]$ va avea toate elementele distincte.
* Pentru alte teste în valoare de $10$ puncte, se garantează că $2 ≤ N ≤ 1 000$.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte.
* Exemplele vor reprezenta teste în valoare de $10$ puncte "din oficiu".
h2. Exemplu
table(example). |_. salsa.in |_. salsa.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
4 1 2 2
| 4
4
4
1
|
| 3
2 3 1
| 3
3
3
|
h3. Explicaţie
...
La primul exemplu:
Pentru o melodie de $1$ secundă, Bulănel poate executa $4$ secvenţe valide de figuri: $1, 2, 3, 4$.
Pentru o melodie de $2$ secunde, Bulănel poate executa $4$ secvenţe valide de figuri: $1-4, 2-1, 3-2, 4-2$.
Pentru o melodie de $3$ secunde, Bulănel poate executa $4$ secvenţe valide de figuri: $1-4-2, 2-1-4, 3-2-1, 4-2-1$.
Pentru o melodie de $4$ secunde, Bulănel poate executa doar o secvenţă validă de figuri: $3-2-1-4$.
== include(page="template/taskfooter" task_id="salsa") ==
