Specsort

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 (nu neapărat minim!).

Date de intrare

Fişierul 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 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 și precizări

• $1 \leq N \leq 50 \ 000$
• Ultima linie din fişier trebuie sa conţină permutarea sortată.

Exemplu

specsort.in

7
7 4 5 1 3 6 2

specsort.out

6 7 4 5 1 3 2
4 5 6 7 1 3 2
1 2 4 5 6 7 3
1 2 3 4 5 6 7

Explicație

Subşirurile mutate la fiecare operaţie sunt:

$6$
$4 \ 5$
$1 \ 2$
$1 \ 2 \ 3$