aranjare

Ion are o stivă cu N elemente și vrea să le sorteze în ordine crescătoare de la bază spre vârf. Pentru a realiza acest lucru, el poate să achiziționeze M stive suplimentare și să efectueze K operații. O operație constă în a lua un element din vârful unei stive și a-l insera în vârful unei alte stive. Ion poate alege convenabil valorile lui M și K. Ajutați-l pe Ion să sorteze elementele astfel încât M*K să aibă valoare cât mai mică și toate valorile să ajungă pe stiva inițială în ordine crescătoare de la bază spre vârf.

Cerinţă

Afișați o secvență de K operații care folosesc M stive suplimentare în așa fel încât să sortați elementele de pe stiva inițială în ordine crescătoare de la bază spre vârf.

Date de intrare

Fișierul de intrare aranjare.in va conține pe primul rând un număr natural nenul N. Pe al doilea rând se află o permutare a mulțimii {1, 2, …, N} ce reprezintă valorile inițiale pe stiva lui Ion. Ultimul element din permutare este cel aflat în vârful stivei.

Date de ieşire

Fișierul de ieșire aranjare.out va conține pe primul rând numerele naturale M și K. Pe următoarele K rânduri se vor scrie perechi de numere s t (câte o pereche pe fiecare rând) reprezentând mutarea elementului din vârful stivei s în vârful stivei t. Se consideră că stiva inițială a lui Ion are indicele 0, iar cele M stive suplimentare au indicii 1, 2, ..., M.
Pentru acordarea punctelor este necesar ca după executarea tuturor operațiilor indicate în fișierul de ieșire, elementele din stiva 0 să fie ordonate crescător de la bază spre vârf.

Restricţii și precizări

• Pentru teste în valoare de 25 de puncte avem N = 980. Pentru celelalte teste avem N = 10 000.

• Pentru testele cu N = 980, punctajele se acordă în modul următor:

• Dacă M * K ≤ 60 000, se acordă 100% din punctajul testului respectiv
• Dacă 60 000 < M * K ≤ 200 000, se acordă 60% din punctajul testului respectiv
• Dacă 200 000 < M * K ≤ 3 000 000 se acordă 20% din punctajul testului respectiv
• Pentru testele cu N = 10 000, punctajele se acordă în modul următor:

• Dacă M * K ≤ 800 000, se acordă 100% din punctajul testului respectiv
• Dacă 800 000 < M * K ≤ 6 000 000, se acordă 60% din punctajul testului respectiv
• Dacă 6 000 000 < M * K ≤ 300 000 000 se acordă 20% din punctajul testului respectiv
   

Exemplu

aranjare.in

3
3 2 1

aranjare.out

2 9
0 1
0 1
0 1
1 2
1 2
1 2
2 0
2 0
2 0

S-au cumpărat 2 stive suplimentare, și s-au efectuat 9 operații.
Primele trei operații mută elementele de pe stiva 0 pe stiva 1.



Următoarele trei operații mută elementele de pe stiva 1 pe stiva 2.



Ultimele trei operații mută elementele înapoi pe stiva 0, în ordinea sortată.