4. Len tak ďalej Adam

Adama už nebaví, ako si z neho všetci robia srandu, že je malý. Preto sa rozhodol to zmeniť – začne posilovať. Tak sa jedného dňa dotrepal do posilovne. Už už išiel robiť prvý set, keď sa pri ňom zastavil tréner: “Servus mladý! Vieš, ako sa to tu robí?”

Adam mu vraví: “Dobrý! Nie, som tu po prvýkrát.”

Tak sa tréner pustil do vysvetľovania: “U nás máme špeciálny cvičiaci plán. Aby si mal dobrý workout, odcvičíš so všetkými činkami, ktoré máme. Ale musíš cvičiť v špeciálnom poradí. Každá činka je zavesená na nejakej inej činke, teda okrem poslednej, tá visí na stojane. Vždy, keď ideš cvičiť, tak si musíš zobrať činku, na ktorej nie sú zavesené žiadne iné. Keď máš na výber, musíš zobrať najľahšiu takú. Keď s činkou docvičíš, nevracaj ju tam kde visela, proste ju polož na kopu na zem. A nezabudni si zapisovať, v akom poradí si cvičil, aby som to mohol skontrolovať.”

Adam je však známy tým, že je veľmi zábudlivý, takže si vždy spomenul na to, že si to má zapisovať, až keď držal činku v ruke. Keďže sa mu nechcelo zdvihnúť činku ku očiam, aby dovidel na číslo hmotnosti, tak si zakaždým zapísal na lepiaci papierik iba váhu tej činky, z ktorej tú svoju odvesil. Potom tento papierik nalepil na stenu. Aby ušetril miesto na stene, ďaľší papierik nalepil vždy na ten predchádzajúci.

Keď nakoniec prišiel tréner a uvidel Adamove zápisky, vôbec nebol spokojný! Chce od neho, aby mu povedal, v akom poradí s činkami cvičil. Chudák Adam teda postupne odlepuje papieriky zo steny, a snaží sa podľa toho zistiť v akom poradí činky používal. Aby upokojil netrpezlivého trénera, potrebuje to rýchlo, teda musí po každom papieriku povedať dalšiu činku, ktorú použil.

Úloha

Máme \(n\) činiek s váhami \(1,\dots,n\). Na začiatku boli usporiadané tak, že jedna bola na stojane, a všetky ostatné viseli na nejakej inej činke. Činky môžu byť zavesené bez ohľadu na váhu, aj ľahšia na ťažšej, aj ťažšia na ľahšej.

Keď Adam ide cvičiť s činkou, dodržiava nasledovné:

1. môže cvičiť len s činkami, na ktorých nie je nič zavesené
2. vždy cvičí s najľahšou dostupnou činkou

Zakaždým si na nový papierik napíše číslo činky, z ktorej túto činku zvesil, a ten potom nalepí na predchádzajúci papierik na stene.

Ako poslednú činku zoberie tú, čo visí na stojane. Keďže nevisí na inej činke, o nej si nezapíše žiaden papierik.

Teraz sú papieriky nalepené na stene – v opačnom poradí ako s nimi Adam cvičil. Adam teraz musí povedať v akom poradí s činkami cvičil od poslednej po prvú, a to tak, že postupne odliepa všetky papieriky a s každým odlepeným musí povedať ďalšiu aspoň jednu činku z tohoto poradia.

Formát vstupu

V prvom riadku vstupu je čislo \(n\) - počet činiek, s ktorými Adam cvičil.

Nasleduje \(n-1\) riadkov. Na každom je číslo od \(1\) po \(n\) zodpovedajúce papieriku na stene, teda o každej činke, s ktorou Adam vtedy cvičil, váha tej činky, na ktorej bola zavesená. Riadkov je \(n-1\) kvôli tomu, že činka na stojane nemá papierik.

Tieto čísla sú napísané v opačnom poradí v akom s nimi Adam cvičil.

Pre \(n\) platia nasledovné obmedzenia:

Formát výstupu

Vypíšte \(n\) riadkov, na \(i\)-tom z nich váhu činky, s ktorou Adam cvičil ako \(i\)-tou poslednou. Teda najprv vypíšte váhu činky, čo bola na stojane, a ako poslednú vypíšte váhu činky, s ktorou Adam cvičil úplne na začiatku.

V sadách 1 až 4 máte dovolené najprv načítať všetky papieriky, a až potom odpovedať. V sadách 5 až 8 musíte hneď po prečítaní každého papierika vypísať aspoň jeden riadok výstupu.

Aby testovanie fungovalo ako má, je nutné po vypísaní každého riadku flushnúť váš výstup, aby ho testovač uvidel. V C++ by malo stačiť cout << nieco << endl;, ale môžete explicitne použiť príkaz cout.flush();. V Pythone vypisujte príkazom print(cislo, flush=True) alebo po vypísaní spravte sys.stdout.flush(). Pre iné jazyky hľadajte ekvivalent k príkazu flush.

Príklady

Takýto vstup môže byť v 5. sade:

>>> 4   #počet činiek
>>> 2   #prvý papier
<<< 2   #posledná činka mala váhu 2
>>> 1
<<< 1
>>> 2
<<< 4
<<< 3   #na konci vypíš uplne prvú činku

v tomto prípade na začiatku boli činky odložené takto:

Adam cvičil s činkami v poradí 3, 4, 1, 2. Na papieriky postupne napísal 2, 1, 2.

Takýto vstup by mohol byť v 1. sade:

>>> 5   #počet činiek
>>> 5   #činky
>>> 1
>>> 1
>>> 1
<<< 5   #posledná činka
<<< 1
<<< 4
<<< 3
<<< 2   #prvá činka

v tomto prípade na začiatku boli činky odložené takto:

Adam cvičil s činkami v poradí 2, 3, 4, 1, 5. Na papieriky postupne napísal 5, 1, 1, 1.