== 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ţă

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