Zadanie 4 - Permutacje

Uwaga! były drobne pomyłki w treści zadania
Dla danej permutacji (a₁, a₂, ..., a_n) liczb od 1 do n, będziemy znajdować jej kodowanie (b₁, b₂, ..., b_n), w których b_i jest równe liczbie wszystkich a_j takich, że j<i oraz a_j>a_i. Inaczej mówiąc coraz to dłuższych fragmentów od początku permutacji piszemy ile jest elementów większych od ostatniego w tym fragmencie.

Wersja prostsza

Dla danej permutacji należy obliczyć jej kodowanie.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita N (1<=N<=500000) - długość permutacji. W drugiej linii znajduje N różnych liczb całkowitych od 1 do N, czyli permutacja, którą trzeba zakodować.

Wyjście

Na standardowe wyjście wypisz N licz całkowitych - kodowanie danej permutacji.

Przykład

Dla wejścia:

7
1 5 2 6 4 7 3

poprawnym wyjściem jest:

0 0 1 0 2 0 4

Wersja trudniejsza

Dla danego kodowania należy znaleźć permutację (należy założyć, że istnieje permutacja, której to jest kodowanie).

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita N (1<=N<=500000) - długość permutacji. W drugiej linii znajduje N liczb całkowitych, które są kodowaniem pewnej permutacji.

Wyjście

Na standardowe wyjście wypisz N licz całkowitych - permutację, której kodowanie jest podane.

Przykład

Dla wejścia:

7
0 0 1 0 2 0 4

poprawnym wyjściem jest:

1 5 2 6 4 7 3

Można wybrać sobie dowolną z tych wersji. Rozwiązania należy wysyłać na adres: parys@mimuw.edu.pl do godziny 17:00 dnia 2.XII.2004.