Permutari II

perm2

==Include(page="template/taskheader" task_id="perm2")==

== include(page="template/taskheader" task_id="perm2") ==

Se considera multimea $A$ formata din elementele $1$, $2$, $3$ … $N$ ({$1$} ≤ $N$ ≤ $20.000$).

Poveste ...

O permutare $P$ este o functie bijectiva definita pe multimea $A$, cu valori in $A$. (adica asociaza in mod unic fiecarui element din $A$ un element unic tot din $A$).
 
Un exemplu de astfel de permutare este ilustrat de tabelul de mai jos
 
table(numbers). |_. $i$    | $1$ |$2$ |$3$ |$4$ |
                |_. $P(i)$ |$2$  |$3$ |$4$ |$1$ |
 
Definim permutarea $P^k^$ astfel:
 
$P^k^(i)$ =
 
* $P(i)$, atunci cand $k=1$
* $P(P^k-1^(i))$, pentru $k > 1$
 
Tabelul de mai jos ilustreaza $P^1^$ si $P^2^$:

h2. Cerinta

table(numbers). |_. $i$       |$1$ |$2$ |$3$ |$4$ |
                |_. $P^1^(i)$ |$2$ |$3$ |$4$ |$1$ |
                |_. $P^2^(i)$ |$3$ |$4$ |$1$ |$2$ |

...

h2. Cerinta

h2. Restrictii

Se da $N$ si o permutare $P$. Sa se gaseasca cel mai mic numar natural $K$ strict pozitiv, astfel incat oricare ar fi $1$ ≤ $i$ ≤ $N$ avem $P^k^(i) = i$ (in alte cuvinte, $P^k^$ sa fie _permutarea identica_ ).

...

h2. Date de intrare

Fisierul $perm2.in$ va contine pe prima linie numarul intreg $N$.
 
Pe urmatoarea linie se scriu $N$ numere naturale distincte, fiecare in intervalul $1$ … {$N$}.

...

h2. Date de iesire

Pe prima linie a fisierului $perm2.out$ se va scrie acel numar $K$ ce indeplineste condiitle impuse.
 
h2. Restrictii si precizari
 
* Pentru testele furnizate $1$ ≤ $K$ ≤ $100.000$
 

...

h2. Exemple

h2. Exemplu

table(example). |_. perm2.in |_. perm2.out |
| 6
1 2 3 4 5 6 | 1 |
| 4
2 3 4 1 | 4 |
| 8
1 5 2 3 4 8 6 7 | 12 |

| perm2.in | perm2.out |
| linia1
linia2
linia3
| linia1
linia2
|

 
==Include(page="template/taskfooter" task_id="perm2")==
 
 

== include(page="template/taskfooter" task_id="perm2") ==

42