== include(page="template/taskheader" task_id="aranjare3") ==
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.
Tanaka 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. Tanaka poate alege convenabil valorile lui $M$ şi $K$. Ajutaţi-l pe Tanaka 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.
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 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.
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 Tanaka. Ultimul element din permutare este cel aflat în vârful stivei.
h2. 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.
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 Tanaka 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
Pentru teste în valoare de 25 de puncte avem N = 980. Pentru celelalte teste avem N = 10 000.
* 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:
o Dacă M * K ≤ 60 000, se acordă 100% din punctajul testului respectiv
o Dacă 60 000 < M * K ≤ 200 000, se acordă 60% din punctajul testului respectiv
o 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:
o Dacă M * K ≤ 800 000, se acordă 100% din punctajul testului respectiv
o Dacă 800 000 < M * K ≤ 6 000 000, se acordă 60% din punctajul testului respectiv
o Dacă 6 000 000 < M * K ≤ 300 000 000 se acordă 20% din punctajul testului respectiv
* 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
