Concurs Albinuta-GP pt elevi | 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 se va găsi valorea N. Pe cea de-a doua linie se vor găsi P[1], ... , P[N].

Date de ieșire

Se va afișa o singură linie, ce conține Q[1], ... , Q[N].

Restricții și precizări

• 1 ≤ N ≤ 100 000
• 1 ≤ P[i] ≤ N
• P[i] ≠ P[j] pentru i ≠ j
• 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 ≤ 1000

Subtask 5 (14 puncte)

• P[1] = N − 1 și P[N] = N

Subtask 6 (35 puncte)

• Fără restricții suplimentare.

Exemple

stdin

4
3 2 4 1

stdout

4 3 2 1

stdin

6
1 4 2 6 5 3

stdout

6 5 4 3 1 2

stdin

10
9 7 8 5 1 4 2 3 6 10

stdout

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: