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

Poveste şi cerinţă...

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.
 
h2. 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.

h2. Date de intrare

Fişierul de intrare $aranjare3.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $aranjare3.out$ ...

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.
 
h2. Restricţii şi precizări

h2. Restricţii

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

h2. Exemplu
table(example). |_. aranjare3.in |_. aranjare3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 3
3 2 1
| 2 9
0 1
0 1
0 1
1 2
1 2
1 2
2 0
2 0
2 0

h3. Explicaţie

|

...

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