Fie n un număr natural şi p=( p₁, p₂, …, p_n) o permutare de ordin n.
Numim grad al unei permutări cel mai mic număr natural k>0, astfel încât
p^k=popop...op=e
(de k ori)
(unde cu e am notat permutare identică, deci permutarea pentru care e(i)=i, pentru orice i=1, 2, ..., n).

Cerinţă

Pentru un n dat, să se determine o permutare de ordin n având grad maxim. Dacă există mai multe soluţii se va determina prima în ordine lexicografică.

Date de intrare

Fişierul de intrare maxperm.in conţine pe prima linie numărul natural nenul n.

Date de ieşire

Fişierul de ieşire maxperm.out va conţine o singură linie pe care vor fi scrise n numere naturale distincte cuprinse între 1 şi n, separate prin câte un spaţiu, reprezentând prima permutare de grad maxim în ordine lexicografică.

Restricţii

0 < n ≤ 2000
Prin operaţia o înţelegem compunerea funcţiilor. Mai exact pop (i)=p ( p (i))), pentru orice i=1, 2, ..., n.

Exemple

maxperm.in	maxperm.out	Explicaţii
5	2 1 4 5 3	Permutarea (2, 1, 4, 5, 3) are gradul 6 (maxim posibil). Există şi alte soluţii, dar aceasta este cea mai mică din punct de vedere lexicografic.
14	2 3 1 5 6 7 4 9 10 11 12 13 14 8

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com