En løpeklubb rekrutterer medlemmer og vokser raskt, med nøyaktig ett nytt medlem som blir med hver dag. Hvert medlem kommer med et bestemt startnivå på ferdighetene sine, og de får tildelt en unik ID basert på rekkefølgen de ankommer i.

På slutten av hver dag liker treneren å beregne et mål han kaller klubbens «totale potensial». Denne verdien er rett og slett summen av de individuelle potensialene til alle nåværende medlemmer. For å holde medlemmene motiverte beregnes potensialet til et medlem gjennom et hypotetisk «hva-hvis»-scenario som involverer én enkelt, intensiv treningsøkt.

I denne tenkte treningsøkten kan et medlem velge å legge ned en viss mengde innsats for midlertidig å øke ferdighetsnivået sitt. For hver $1$ enhet innsats de bruker, øker ferdighetsnivået deres med nøyaktig $1$ enhet. Til gjengjeld får de $1$ enhet «lykke» for hvert annet medlem som for øyeblikket er i klubben og som:

• ble med i klubben strengt etter dem; og
• opprinnelig var strengt dyktigere enn dem, men nå har blitt tatt igjen eller forbigått takket være treningsøkten.

Merk at under denne beregningen økes kun ferdighetsnivået til dette ene medlemmet, mens ferdighetsnivåene til alle andre medlemmer forblir låst til sine opprinnelige verdier.

Potensialet til et enkelt medlem er definert som den maksimalt mulige verdien av nettogevinsten deres (lykke minus innsats) som de kan oppnå ved å velge innsatsnivået sitt optimalt. Disse treningsøktene er helt teoretiske; de brukes kun til trenerens daglige rapport, og medlemmenes faktiske ferdighetsnivåer forblir uendret fra dag til dag.

Din oppgave er å hjelpe treneren med å beregne klubbens totale potensial på slutten av hver dag i rekrutteringsperioden.

Inndata

Den første linjen i inndataene inneholder et heltall $n$ ($1 \le n \le 10^5$), som representerer antall dager klubben rekrutterer medlemmer.

Den andre linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), der $a_i$ er det opprinnelige ferdighetsnivået til medlemmet som blir med på dag $i$.

Utdata

Skriv ut $n$ heltall på én enkelt linje. Det $k$-te heltallet skal være klubbens totale potensial på slutten av dag $k$.

Eksempler

Inndata 1

8
1 2 3 1 2 3 2 3

Utdata 1

0 0 0 0 1 3 5 9

Inndata 2

1
1

Utdata 2

0

Forklaring

Forklaring av eksempel 1: På dag $5$ er det $5$ medlemmer med ferdighetsnivåene $[1, 2, 3, 1, 2]$. For medlem $1$: Det er $3$ medlemmer som ble med senere med strengt høyere ferdigheter: medlem $2$, medlem $3$ og medlem $5$. Det maksimale potensialet for medlem $1$ er $1$, oppnådd ved en av følgende strategier:

• Hvis medlem $1$ betaler $1$ enhet innsats, blir ferdigheten deres $2$. De vil ta igjen eller forbigå medlem $2$ og medlem $5$. Lykken er $2$ enheter, og gevinsten er $2 - 1 = 1$ enhet.
• Hvis medlem $1$ betaler $2$ enheter innsats, blir ferdigheten deres $3$. De vil ta igjen eller forbigå medlemmene $2$, $3$ og $5$. Lykken er $3$ enheter, og gevinsten er $3 - 2 = 1$ enhet.

De andre medlemmene har maksimalt potensial $0$. Dermed er det totale potensialet for dag $5$ lik $1$.

På dag $8$ er det $8$ medlemmer med ferdighetsnivåene $[1, 2, 3, 1, 2, 3, 2, 3]$. De optimale innsatsene er $[2, 1, 0, 2, 1, 0, 1, 0]$ og de tilsvarende maksimale potensialene er $[4, 2, 0, 2, 1, 0, 0, 0]$.