gp

GP

== include(page="template/taskheader" task_id="gp") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $gp.in$ ...

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]$.

h2. Date de ieşire

În fişierul de ieşire $gp.out$ ...

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

h2. 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 &le; p &le; K$}) astfel încât $A[p] > B[p]$ şi $A[i] = B[i]$ pentru orice $1 &le; i < p$.

h2. Exemplu

h3. Subtask 1 (6 puncte)

table(example). |_. gp.in |_. gp.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

* $N ≤ 10$
 
h3. Subtask 2 (7 puncte)
 
* $N ≤ 18$
 
h3. Subtask 3 (25 puncte)

h3. Explicaţie

* $N ≤ 100$

...

h3. Subtask 4 (13 puncte)
 
* $N ≤ 1 000$
 
h3. Subtask 5 (14 puncte)
 
* $P[1] = N - 1$ şi $P[N] = N$
 
h3. Subtask 6 (35 puncte)
 
* Fără restricţii suplimentare.
 
h2. Exemple
 
table(example). |_. 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 |
 
h3. Explicaţii
 
În primul exemplu, rafturile au următoarele stări:
 
<tex>
\vspace{1em}
\begin{tabular}{l | l}
    \toprule
    \textbf{Raftul A} & \textbf{Raftul B} \\
    \midrule
    3 2 4 1 & \\ \hline
    2 4 1 & 3 \\ \hline
    4 1 & 3 2 \\ \hline
    4 & 3 2 1 \\ \hline
     & 4 3 2 1 \\
    \bottomrule
\end{tabular}
</tex>
 
În al doilea exemplu, rafturile au următoarele stări:
 
<tex>
\vspace{1em}
\begin{tabular}{l | l}
    \toprule
    \textbf{Raftul A} & \textbf{Raftul B} \\
    \midrule
    1 4 2 6 5 3 & \\ \hline
    4 2 6 5 3 & 1 \\ \hline
    4 2 6 5 & 3 1 \\ \hline
    2 6 5 & 4 3 1 \\ \hline
    6 5 & 4 3 1 2 \\ \hline
    6 & 5 4 3 1 2 \\ \hline
    & 6 5 4 3 1 2 \\
    \bottomrule
\end{tabular}
</tex>
‏‏‎ ‎

== include(page="template/taskfooter" task_id="gp") ==