6. O introvertných a extrovertných holuboch

POZOR: táto úloha má neštandardný spôsob hodnotenia. Viac sa dozviete v časti Hodnotenie.

Pán Dirichlet je veľkochovateľ poštových holubov. Vo svojich početných holubníkoch chová obrovské množstvo holubov, z ktorých občas niektoré predá malochovateľom.

Dávid sa chce stať malochovateľom poštových holubov. Na záhrade si postavil celý rad holubníkov, ktoré (v duchu najlepších chovateľských tradícií) očísloval číslami \(1, 2, 3, \dots\). Následne si u pána Dirichleta objednal \(n\) holubov.

Pán Dirichlet teda Dávidovi pekne po jednom poslal¹ \(n\) holubov.

Holuby sú teraz na ceste a Dávid sa pripravuje na ich prijatie. Plán je jednoduchý: holuby budú po jednom prilietať (v poradí, v akom boli poslané, keďže, ako je všeobecne známe, slušné poštové holuby sa navzájom nepredbiehajú) a vždy, keď nejaký holub priletí, Dávid ho strčí do niektorého z holubníkov. To však nemôže robiť len tak halabala. Sťahovanie sa z jedného holubníka do druhého je totiž pre takého holuba veľká udalosť a ak sa to urobí zle, holub si nikdy na svoj nový domov nezvykne, začne chradnúť a predčasne umrie. To, či sa holub v novom domove dobre aklimatizuje, sa riadi nasledovnými pravidlami:

• Každý holub má nejakú extroverciu. Extrovercia holuba je nezáporné celé číslo, ktoré je pri introvertných holuboch nízke a pri extrovertných holuboch vysoké.

• Keď holuba s extroverciou \(e\) nasťahujeme do nového holubníka, v ktorom už býva presne \(e\) iných holubov, náš holub sa do tejto spoločnosti bez problémov začlení a rýchlo (hneď) si na nový domov zvykne. Ak je však v holubníku iný počet holubov ako \(e\) (menej, alebo viac), náš holub sa v kolektíve necíti dobre a na nový domov si nikdy nezvykne.

• Keď si už raz holub zvykne na svoj holubník (čo sa stane buď hneď po jeho príchode, alebo nikdy), nevadí mu, ak do tohto holubníka pridávame aj nové holuby.

Pán Dirichlet, ako dobrý chovateľ, pozná extrovercie všetkých svojich holubov a spolu s faktúrou poslal² Dávidovi aj zoznam extrovercií odoslaných holubov, v poradí, v akom ich poslal. Dávid sa teraz na tento zoznam pozerá a snaží sa naplánovať, ako holuby napchať do holubníkov tak, aby sa všetky dobre aklimatizovali. Pomôžte mu!

Úloha

Na vstupe dostanete postupnosť \(n\) čísel \(e_1, e_2, \dots, e_n\) – extrovercie holubov v poradí, v akom budú prilietať. Nájdite takú postupnosť prirodzených čísel \(h_1, h_2, \dots, h_n\), že ak Dávid strčí prvého holuba do holubníka číslo \(h_1\), druhého do holubníka číslo \(h_2\), tretieho do \(h_3\) atď., všetky holuby si dobre zvyknú. Inými slovami, pre každé \(i \in \{1, 2, \dots, n\}\) musí platiť, že presne \(e_i\) spomedzi čísel \(h_1, h_2, \dots, h_{i-1}\) sa rovná číslu \(h_i\). Môžete predpokladať, že Dávid má aspoň \(n\) holubníkov a aspoň jedna vhodná postupnosť existuje (pán Dirichlet je dobrý chovateľ a neposlal by svoje holuby tak, aby boli niektoré z nich odsúdené na chradnutie).

Formát vstupu

V prvom riadku vstupu je celé číslo \(n\) (\(1 \leq n \leq 1\,000\,000\)). V druhom riadku je \(n\) medzerami oddelených nezáporných celých čísel \(e_1, e_2, \dots, e_n\) – extrovercie holubov. Pre každé zmysluplné \(i\) platí \(0 \leq e_i \leq {n-1}\).

Formát výstupu

Vypíšte jeden riadok a v ňom \(n\) celých čísel oddelených medzerami – jednu vhodnú postupnosť \(h_1, h_2, \dots, h_n\). Pre každé zmysluplné \(i\) musí platiť \(1 \leq h_i \leq n\) (aj tak určite nebudete potrebovať viac ako \(n\) holubníkov). Ak je možných riešení viac, vypíšte ľubovoľné z nich.

Hodnotenie

V tejto úlohe budeme primárne hodnotiť pamäťovú zložitosť vášho algoritmu a až sekundárne časovú. Na časovú zložitosť budeme prihliadať iba tak, ako v iných úlohách prihliadame na pamäťovú (teda algoritmus s lepšou pamäťovou a horšou časovou zložitosťou považujeme za lepší, pokiaľ nie je jeho časová zložitosť absurdne veľká). Tomu zodpovedá aj pomerne voľný časový limit a veľmi malý pamäťový limit (najväčšie vstupy sa vám nezmestia do pamäte) v praktickom testovaní.

Pre jednotlivé vstupné sady platí:

V sade č. 3 navyše v každom vstupe platí, že existuje riešenie využívajúce nanajvýš \(1\,000\) holubníkov.

Príklad

Input:

4
0 0 0 0

Output:

1 2 3 4

Každý holub musí ísť do nového holubníka. Dobrým riešením je napríklad aj 4 3 2 1.

Input:

5
0 1 2 3 4

Output:

3 3 3 3 3

Všetky holuby musíme dať do rovnakého holubníka.

Input:

8
0 0 1 0 1 2 3 2

Output:

4 2 4 3 2 2 2 4

Jedno z mnohých možných riešení.