Fișierul intrare/ieșire	specsort.in, specsort.out	Sursă	Lot Sovata 2014
Autor	Cristian Lambru	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	0.6 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Specsort (lot liceu)

Autor: Cristian Lambru

Se consideră o permutare a mulțimii {1, 2, …, N}. Pentru această permutare se definește un singur tip de operație: se extrage din permutare un subșir, iar elementele subșirului se adaugă (în aceeași ordine) la începutul permutării. De exemplu, pentru permutarea (3, 1, 5, 2, 6, 4), se poate alege subșirul (1, 2, 4) care se introduce la începutul permutării, obținându-se (1, 2, 4, 3, 5, 6).

Cerință

Să se sorteze elementele din permutare efectuând un număr cât mai mic de operații.

Date de intrare

Fișierul de intrare specsort.in conține pe prima linie numărul natural N, iar pe linia a doua, separate prin câte un spațiu, cele N elemente ale permutării.

Date de ieșire

Fișierul de ieșire specsort.out conține un număr de linii egal cu numărul de operații efectuate. Pe a i-a dintre aceste linii se găsesc câte N numere naturale separate printr-un spațiu, reprezentând permutarea obținută după aplicarea celei de a i-a operație.

Restricții

• 1 ≤ N ≤ 50 000
• Ultima linie din fișier trebuie să conțină permutarea sortată.
• Enunțul oficial nu specifică cum se acordă punctajul. Veți primi punctajul pentru un test dacă veți rezolva problema în cel mult 25 de pași.

Exemplu

Explicație

Subșirurile mutate la fiecare operație sunt:
6
4 5
1 2
1 2 3