| 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:
![\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}](https://www.infoarena.ro/static/images/latex/8b49ce780f15f3a26a8d593e2b88ce86_47.69998pt.gif "\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}")
