Pentru un număr natural nenul n, să considerăm toate numerele naturale nenule mai mici sau egale cu n, luând fiecare număr de câte două ori: 1, 1, 2, 2, 3, 3, ... , n, n. Aceste numere le amestecăm aleator, şi le aranjăm pe două linii a câte n elemente. Structura astfel obţinută o vom numi o bipermutare. În figurile 1, 2 şi 3 avem câte un exemplu de bipermutare pentru n=5.

O bipermutare este perfectă, dacă ambele linii ale structurii reprezintă câte o permutare (vezi figurile 2 şi 3).

Prin mutare pe poziţia p, înţelegem interschimbarea elementelor de pe aceeaşi coloană p. În exemplele de mai jos, bipermutarea perfectă din figura 2 s-a obţinut din bipermutarea din figura 1, aplicând o mutare pe poziţa 2. Bipermutarea perfectă din figura 3 s-a obţinut din bipermutarea din figura 1, aplicând mutări pe poziţiile 1, 2, 4 şi 5.

Cerința

Cunoscând o bipermutare, determinaţi:

• numărul bipermutărilor perfecte distincte ce se pot obţine prin mutări;
• numărul minim de mutări prin care se poate obţine o bipermutare perfectă;
• o bipermutare perfectă obţinută din bipermutarea iniţială.

Date de intrare

Fișierul de intrare biperm.in conține pe prima linie valoarea lui n. Următoarele două linii conţin, fiecare, câte n elemente separate prin câte un spaţiu, formând o bipermutare.

Date de ieșire

Fișierul de ieșire biperm.out va conține:

• pe prima linie două numere naturale separate printr-un spaţiu, reprezentând numărul bipermutărilor perfecte distincte ce se pot obţine din bipermutarea dată, respectiv numărul minim de mutări prin care se poate obţine o bipermutare perfectă;
• pe următoarele două linii se vor tipări câte n numere separate prin spaţiu, reprezentând o bipermutare perfectă obţinută din bipermutarea dată.

Restricții și precizări

• 2 < n ≤ 10 000;
• calculul corect al numărului bipermutărilor perfecte distincte valorează 30% din punctaj;
• calculul corect al numărului minim de mutări valorează 10% din punctaj;
• tipărirea unei bipermutări perfecte valorează 60% din punctaj. Pot exista mai multe soluţii, se va admite orice soluţie corectă;
• se garantează că numărul bipermutărilor perfecte distincte nu depăşeşte 2 000 000 000 pentru niciun test.
• pentru 40% din teste n ≤ 20
• pentru 40% din teste 20 < n ≤ 400
• pentru 20% din teste 400 < n ≤ 10 000

Exemplu:

biperm.in

5
1 5 5 3 4
3 2 2 4 1

biperm.out

4 1
1 2 5 3 4
3 5 2 4 1

Explicație

Sunt 4 permutări perfecte. Numărul minim de mutări este 1 şi există două soluţii cu număr minim de mutări:

1 2 5 3 4            1 5 2 3 4
3 5 2 4 1     şi      3 2 5 4 1

Celelalte două soluţii, ce nu se obţin din număr minim de mutări sunt:

3 2 5 4 1            3 5 2 4 1
1 5 2 3 4     şi      1 2 5 3 4

Pentru a treia cerinţă oricare dintre cele 4 soluţii este acceptată.