Un club de course à pied recrute des membres et se développe rapidement, avec exactement un nouveau membre rejoignant le club chaque jour. Chaque membre arrive avec un niveau de compétence initial spécifique et se voit attribuer un identifiant unique basé sur son ordre d'arrivée.

À la fin de chaque journée, l'entraîneur aime calculer une mesure qu'il appelle le « potentiel total » du club. Cette valeur est simplement la somme des potentiels individuels de tous les membres actuels. Pour garder les membres motivés, le potentiel d'un membre est calculé à travers un scénario hypothétique impliquant un seul entraînement intense.

Dans cet entraînement imaginaire, un membre peut choisir de fournir une certaine quantité d'effort pour augmenter temporairement son niveau de compétence. Pour chaque unité ($1$) d'effort dépensée, son niveau de compétence augmente d'exactement $1$ unité. En retour, il gagne $1$ unité de « bonheur » pour chaque autre membre actuellement dans le club qui :

• a rejoint le club strictement après lui ; et
• était à l'origine strictement plus compétent que lui, mais a maintenant été rattrapé ou dépassé grâce à l'entraînement.

Notez que pendant ce calcul, seul le niveau de compétence de ce membre est augmenté, tandis que les niveaux de compétence de tous les autres membres restent fixés à leurs valeurs d'origine.

Le potentiel d'un seul membre est défini comme la valeur maximale possible de son gain net (bonheur moins effort) qu'il pourrait atteindre en choisissant son niveau d'effort de manière optimale. Ces entraînements sont entièrement théoriques ; ils ne sont utilisés que pour le rapport quotidien de l'entraîneur, et les niveaux de compétence réels des membres restent inchangés d'un jour à l'autre.

Votre tâche est d'aider l'entraîneur à calculer le potentiel total du club à la fin de chaque journée de la période de recrutement.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 10^5$), représentant le nombre de jours pendant lesquels le club recrute des membres.

La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), où $a_i$ est le niveau de compétence initial du membre qui rejoint le club le jour $i$.

Sortie

Affichez $n$ entiers sur une seule ligne. Le $k$-ième entier doit être le potentiel total du club à la fin du jour $k$.

Exemples

Entrée 1

8
1 2 3 1 2 3 2 3

Sortie 1

0 0 0 0 1 3 5 9

Entrée 2

1
1

Sortie 2

0

Notes

Explication de l'exemple 1 : Le jour $5$, il y a $5$ membres avec des niveaux de compétence $[1, 2, 3, 1, 2]$. Pour le membre $1$ : Il y a $3$ membres arrivés plus tard avec des compétences strictement supérieures : le membre $2$, le membre $3$ et le membre $5$. Le potentiel maximal du membre $1$ est $1$, atteint par l'une des stratégies suivantes :

• Si le membre $1$ fournit $1$ unité d'effort, sa compétence devient $2$. Il rattrapera ou dépassera le membre $2$ et le membre $5$. Le bonheur est de $2$ unités, et le gain est de $2 - 1 = 1$ unité.
• Si le membre $1$ fournit $2$ unités d'effort, sa compétence devient $3$. Il rattrapera ou dépassera les membres $2$, $3$ et $5$. Le bonheur est de $3$ unités, et le gain est de $3 - 2 = 1$ unité.

Les autres membres ont un potentiel maximal de $0$. Par conséquent, le potentiel total pour le jour $5$ est $1$.

Le jour $8$, il y a $8$ membres avec des niveaux de compétence $[1, 2, 3, 1, 2, 3, 2, 3]$. Les efforts optimaux sont $[2, 1, 0, 2, 1, 0, 1, 0]$ et les potentiels maximaux correspondants sont $[4, 2, 0, 2, 1, 0, 0, 0]$.