Fişierul intrare/ieşire:	gp.in, gp.out	Sursă	OSEPI Baraj Seniori 1
Autor	Ionel-Vasile Pit-Rada	Adăugată de	Matteo Verzotti •Matteoalexandru
Timp execuţie pe test	0.25 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

GP

Bunicul GrandPa (abreviat GP) a fost foarte pasionat de concursurile de algoritmică. În tinereţe, acesta a participat la N prestigioase competiţii, iar la fiecare dintre ele a reuşit să se claseze pe prima poziţie şi să câştige câte un trofeu. Pentru a le identifica mai uşor, bunicul le-a atribuit trofeelor câte un număr între 1 şi N, astfel încât oricăror două trofee distincte le-au fost atribuite numere distincte.

Cele N trofee stau acum aranjate în casa bunicului pe raftul A. Cel de-al i-lea trofeu (1 ≤ i ≤ N), în ordine de la stânga la dreapta, este cel cu numărul P[i]. Bunicul va fi vizitat în curând de nepoţi, pe care vrea să îi impresioneze cu trofeele sale. De aceea, el va muta trofeele de pe raftul A pe raftul B (care este iniţial gol), prin aplicarea repetată a următoarei operaţii:

• Se alege fie trofeul cel mai din stânga de pe raftul A, fie trofeul cel mai din dreapta de pe raftul A.
• Acest trofeu este mutat pe raftul B, fie la stânga tuturor trofeelor deja aflate pe raftul B, fie la dreapta acestora. Dacă raftul B este gol, trofeul se poate aşeza oriunde.

Această operaţie se va aplica până când raftul A devine gol, iar toate trofeele au fost mutate pe raftul B.

După ce se efectuează toate mutările, fie Q[i] (1 ≤ i ≤ N) cel de-al i-lea trofeu de pe raftul B, în ordine de la stânga la dreapta. Pentru a-şi impresiona nepoţii, bunicul doreşte să efectueze operaţiile de mutare astfel încât şirul Q să fie mai mare lexicografic decât orice alt şir Q' care s-ar putea obţine prin metoda descrisă. Aflaţi acest şir Q maxim lexicografic.

Date de intrare

Pe prima linie a fişierului de intrare gp.in se va găsi valorea N. Pe cea de-a doua linie se vor găsi P[1], ... , P[N].

Date de ieşire

În fişierul de ieşire gp.out se va afişa o singură linie, ce conţine Q[1], ... , Q[N].

Restricţii

• 1 ≤ N ≤ 100 000
• 1 ≤ P[i] ≤ N
• Un şir A de lungime K este mai mare lexicografic decât un şir B de lungime K dacă există o poziţie p (1 ≤ p ≤ K) astfel încât A[p] > B[p] şi A[i] = B[i] pentru orice 1 ≤ i < p.

Subtask 1 (6 puncte)

• N ≤ 10

Subtask 2 (7 puncte)

• N ≤ 18

Subtask 3 (25 puncte)

• N ≤ 100

Subtask 4 (13 puncte)

• N ≤ 1 000

Subtask 5 (14 puncte)

• P[1] = N - 1 şi P[N] = N

Subtask 6 (35 puncte)

• Fără restricţii suplimentare.

Exemple

gp.in	gp.out
4 3 2 4 1	4 3 2 1
6 1 4 2 6 5 3	6 5 4 3 1 2
10 9 7 8 5 1 4 2 3 6 10	10 9 7 8 6 5 3 2 4 1

Explicaţii

În primul exemplu, rafturile au următoarele stări:

În al doilea exemplu, rafturile au următoarele stări:

‏‏‎ ‎

Cum se trimit solutii?