Klub biegowy rekrutuje członków i szybko się rozwija – każdego dnia dołącza dokładnie jeden nowy członek. Każdy członek przychodzi z określonym początkowym poziomem umiejętności i otrzymuje unikalny identyfikator na podstawie kolejności dołączenia.

Na koniec każdego dnia Trener lubi obliczać wskaźnik, który nazywa „całkowitym potencjałem” klubu. Wartość ta jest po prostu sumą indywidualnych potencjałów wszystkich obecnych członków. Aby utrzymać motywację członków, potencjał członka obliczany jest w ramach hipotetycznego scenariusza „co by było, gdyby”, obejmującego pojedynczy, intensywny trening.

W tym wyimaginowanym treningu członek może zdecydować się na włożenie pewnego wysiłku, aby tymczasowo podnieść swój poziom umiejętności. Za każde zużyte $1$ (jednostkę wysiłku) jego poziom umiejętności wzrasta o dokładnie $1$ jednostkę. W zamian zyskuje $1$ jednostkę „szczęścia” za każdego innego obecnego członka klubu, który:

• dołączył do klubu ściśle później niż on; oraz
• początkowo miał ściśle wyższe umiejętności niż on, ale dzięki treningowi został przez niego dogoniony lub prześcignięty.

Zauważ, że podczas tych obliczeń zwiększany jest tylko poziom umiejętności tego jednego członka, podczas gdy poziomy umiejętności wszystkich pozostałych członków pozostają zamrożone na swoich początkowych wartościach.

Potencjał pojedynczego członka jest zdefiniowany jako maksymalna możliwa wartość jego zysku netto (szczęście minus wysiłek), jaką mógłby osiągnąć przy optymalnym wyborze poziomu wysiłku. Treningi te są całkowicie teoretyczne; służą wyłącznie do codziennego raportu Trenera, a rzeczywiste poziomy umiejętności członków nie zmieniają się z dnia na dzień.

Twoim zadaniem jest pomóc Trenerowi obliczyć całkowity potencjał klubu na koniec każdego dnia okresu rekrutacyjnego.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą $n$ ($1 \le n \le 10^5$), oznaczającą liczbę dni, przez które klub rekrutuje członków.

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), gdzie $a_i$ to początkowy poziom umiejętności członka dołączającego w dniu $i$.

Wyjście

Wypisz $n$ liczb całkowitych w jednym wierszu. $k$-ta liczba całkowita powinna oznaczać całkowity potencjał klubu na koniec dnia $k$.

Przykłady

Wejście 1

8
1 2 3 1 2 3 2 3

Wyjście 1

0 0 0 0 1 3 5 9

Wejście 2

1
1

Wyjście 2

0

Uwagi

Wyjaśnienie przykładu 1: W dniu $5$ jest $5$ członków o poziomach umiejętności $[1, 2, 3, 1, 2]$. Dla członka $1$: Jest $3$ członków, którzy dołączyli później i mają ściśle wyższe umiejętności: członek $2$, członek $3$ oraz członek $5$. Maksymalny potencjał członka $1$ wynosi $1$ i jest osiągany za pomocą jednej z poniższych strategii:

• Jeśli członek $1$ włoży $1$ jednostkę wysiłku, jego umiejętności wzrosną do $2$. Dogoni lub prześcignie członka $2$ oraz członka $5$. Szczęście wyniesie $2$ jednostki, a zysk $2 - 1 = 1$ jednostkę.
• Jeśli członek $1$ włoży $2$ jednostki wysiłku, jego umiejętności wzrosną do $3$. Dogoni lub prześcignie członków $2$, $3$ oraz $5$. Szczęście wyniesie $3$ jednostki, a zysk $3 - 2 = 1$ jednostkę.

Pozostali członkowie mają maksymalny potencjał równy $0$. Zatem całkowity potencjał w dniu $5$ wynosi $1$.

W dniu $8$ jest $8$ członków o poziomach umiejętności $[1, 2, 3, 1, 2, 3, 2, 3]$. Optymalne wysiłki to $[2, 1, 0, 2, 1, 0, 1, 0]$, a odpowiadające im maksymalne potencjały to $[4, 2, 0, 2, 1, 0, 0, 0]$.