Zadanie

Escape character

Počet bodov: 35, časový limit: 2000ms

V reťazcoch reprezentovaných v počítači sa často vyskytujú špeciálne znaky, ktoré nie sú vypísané, ale vykonávajú nejakú funkciu, napríklad koniec riadku: \n. Aby sme s nimi vedeli pohodlne manipulovať, reprezentujeme ich ako niektorý obyčajný, vypísateľný znak, pred ktorý vložíme tzv. ‘escape’ – v horeuvedenom príklade znak \.

Buj si na miestnom trhu kúpil reťazec \(S\) dĺžky \(n\) na (vraj zcela vrámci zákona) domácu manipuláciu.

Nedržal sa pri tom starého príslovia ‘nekupuj reťazec vo vreci’.

Keď prišiel domov a vytiahol reťazec z vreca, z hrôzou zistil, že jeho znaky nenasledujú žiadne známe kódovanie. Jediné, čo vedel, je očíslovať jeho znaky od \(0\) po \(n-1\).

Ničto, nejak ten reťazec predsa už len zmanipuluje, pomyslel si Buj. Bál sa však, že ho na trhu podviedli a predali mu nekvalitný reťazec – taký, ktorý keď vypíšeme, tak je lexikograficky veľký.

To však závisí od toho, ktorý znak v reťazci je ten ‘escape’. Pre každý znak ho zaujíma, ako veľmi dobrý reťazec by to bol, ak by zrovna tento znak bol escape. Reťazec poslal poštou nám, a my sme veľmi dobrí v hľadaní lacnej pracovnej sily…

Vstup a výstup

V prvom riadku vstupu je číslo \(n\): počet znakov v Bujovom reťazci. V druhom riadku vstupu je permutácia čísel \(0, \cdots, n-1\) popisujúca Bujov reťazec \(S\). Znaky sú očíslované od (lexikograficky) najmenšieho po najväčší.

Escape znak funguje nasledovne: ak je to posledný znak v reťazci, nemá žiadny efekt, a je stále vypísaný na výstupe. Inak sú vypísané všetky znaky okrem neho a znaku bezprostredne za ním. Pre lepšie pochopenie si prečítajte príklad.

Nech \(S_i\) je reťazec ktorý sa vypíše na výstup, ak zvolíme znak číslo \(i\) ako escape v Bujovom reťazci \(S\). Zoraďme si všetky takéto reťazce lexikograficky od najmenšieho po najväčší, a nech \(p_i\) je pozícia reťazca \(S_i\) v tomto zoradení, začínajúc od nuly.

Vypíšte do jedného riadku \(p_0, p_1, \cdots, p_{n-1}\), oddelené medzerami. Teda postupne vypíšte odpovede na otázky:
- “Koľko reťazcov spomedzi \(S_0, \ldots, S_{n-1}\) je lexikograficky menších ako ten, ktorý by sme vypísali, ak je znak \(0\) escape?”
- “Koľko by ich bolo, ak by znak \(1\) bol escape?”
- “Čo ak znak \(2\) je escape?”
- …

Dajte si pozor na to, že \(i\)-ta odpoveď sa vzťahuje ku znaku číslo \(i\), nie ku v poradí \(i\)-temu znaku (rátajúc od \(0\)).

V polovici vstupov platí \(1 \leq n \leq 3\,000\), v druhej polovici \(1 \leq n \leq 10^6\).

Príklad

Input:

3
0 1 2

Output:

2 0 1

Ak je znak \(0\) escape, vypísali by sme reťazec \(2\). Ak je znak \(1\) escape, vypísali by sme \(0\). Ak je znak \(2\) escape, vypísali by sme \(0~1~2\).

Zoradené reťazce sú teda \([0, 0~1~2, 2]\). Máme teda dva reťazce menšie ako \(S_0\), žiadne menšie ako \(S_1\), a jeden menší ako \(S_2\).