Ein Laufclub wirbt Mitglieder an und wächst rasant, wobei jeden Tag genau ein neues Mitglied beitritt. Jedes Mitglied bringt ein bestimmtes anfängliches Fähigkeitsniveau mit und erhält basierend auf der Reihenfolge seines Eintreffens eine eindeutige ID.

Am Ende jedes Tages berechnet der Trainer gerne eine Kennzahl, die er das „Gesamtpotenzial“ des Clubs nennt. Dieser Wert ist einfach die Summe der individuellen Potenziale aller aktuellen Mitglieder. Um die Mitglieder zu motivieren, wird das Potenzial eines Mitglieds durch ein hypothetisches „Was-wäre-wenn“-Szenario berechnet, das ein einziges, intensives Training beinhaltet.

In diesem imaginären Training kann ein Mitglied wählen, eine bestimmte Menge an Anstrengung zu investieren, um sein Fähigkeitsniveau vorübergehend zu steigern. Für jede $1$ Einheit an Anstrengung, die es aufwendet, steigt sein Fähigkeitsniveau um genau $1$ Einheit. Im Gegenzug erhält es $1$ Einheit „Glück“ für jedes andere aktuell im Club befindliche Mitglied, das:

• dem Club strikt nach ihm beigetreten ist; und
• ursprünglich strikt fähiger war als es selbst, aber dank des Trainings nun eingeholt oder übertroffen wurde.

Beachten Sie, dass während dieser Berechnung nur das Fähigkeitsniveau dieses einen Mitglieds erhöht wird, während die Fähigkeitsniveaus aller anderen Mitglieder fest auf ihren ursprünglichen Werten bleiben.

Das Potenzial eines einzelnen Mitglieds ist definiert als der maximal mögliche Wert seines Nettogewinns (Glück minus Anstrengung), den es durch optimale Wahl seines Anstrengungsniveaus erreichen könnte. Diese Trainingseinheiten sind rein theoretisch; sie werden nur für den täglichen Bericht des Trainers verwendet, und die tatsächlichen Fähigkeitsniveaus der Mitglieder bleiben von Tag zu Tag unverändert.

Ihre Aufgabe ist es, dem Trainer zu helfen, das Gesamtpotenzial des Clubs am Ende jedes Tages des Rekrutierungszeitraums zu berechnen.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $n$ ($1 \le n \le 10^5$), die die Anzahl der Tage darstellt, an denen der Club Mitglieder rekrutiert.

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), wobei $a_i$ das anfängliche Fähigkeitsniveau des Mitglieds ist, das an Tag $i$ beitritt.

Ausgabe

Geben Sie $n$ ganze Zahlen in einer einzigen Zeile aus. Die $k$-te ganze Zahl sollte das Gesamtpotenzial des Clubs am Ende von Tag $k$ sein.

Beispiele

Eingabe 1

8
1 2 3 1 2 3 2 3

Ausgabe 1

0 0 0 0 1 3 5 9

Eingabe 2

1
1

Ausgabe 2

0

Hinweis

Erklärung zu Beispiel 1: An Tag $5$ gibt es $5$ Mitglieder mit den Fähigkeitsniveaus $[1, 2, 3, 1, 2]$. Für Mitglied $1$: Es gibt $3$ Mitglieder, die später mit strikt höheren Fähigkeiten beigetreten sind: Mitglied $2$, Mitglied $3$ und Mitglied $5$. Das maximale Potenzial für Mitglied $1$ beträgt $1$ und wird durch eine der folgenden Strategien erreicht:

• Wenn Mitglied $1$ $1$ Einheit Anstrengung investiert, wird seine Fähigkeit zu $2$. Es holt Mitglied $2$ und Mitglied $5$ ein oder übertrifft sie. Das Glück beträgt $2$ Einheiten, und der Gewinn ist $2 - 1 = 1$ Einheit.
• Wenn Mitglied $1$ $2$ Einheiten Anstrengung investiert, wird seine Fähigkeit zu $3$. Es holt die Mitglieder $2$, $3$ und $5$ ein oder übertrifft sie. Das Glück beträgt $3$ Einheiten, und der Gewinn ist $3 - 2 = 1$ Einheit.

Die anderen Mitglieder haben ein maximales Potenzial von $0$. Daher beträgt das Gesamtpotenzial für Tag $5$ gleich $1$.

An Tag $8$ gibt es $8$ Mitglieder mit den Fähigkeitsniveaus $[1, 2, 3, 1, 2, 3, 2, 3]$. Die optimalen Anstrengungen sind $[2, 1, 0, 2, 1, 0, 1, 0]$ und die entsprechenden maximalen Potenziale sind $[4, 2, 0, 2, 1, 0, 0, 0]$.