En löparklubb rekryterar medlemmar och växer snabbt, med exakt en ny medlem som går med varje dag. Varje medlem har en specifik initial skicklighetsnivå och tilldelas ett unikt ID baserat på i vilken ordning de anländer.

I slutet av varje dag gillar tränaren att beräkna ett mått som han kallar klubbens "totala potential". Detta värde är helt enkelt summan av de individuella potentialerna för alla nuvarande medlemmar. För att hålla medlemmarna motiverade beräknas en medlems potential genom ett hypotetiskt "tänk om"-scenario som involverar ett enda intensivt träningspass.

I detta tänkta träningspass kan en medlem välja att lägga ner en viss mängd ansträngning för att tillfälligt höja sin skicklighetsnivå. För varje $1$ enhet ansträngning de förbrukar ökar deras skicklighetsnivå med exakt $1$ enhet. I gengäld får de $1$ enhet "lycka" för varje annan medlem som för närvarande är med i klubben och som:

• gick med i klubben strikt efter dem; och
• ursprungligen var strikt skickligare än de var, men nu har blivit ikapphetsad eller passerad tack vare träningspasset.

Observera att under denna beräkning ökas endast den medlemmens skicklighetsnivå, medan skicklighetsnivåerna för alla andra medlemmar förblir låsta vid sina ursprungliga värden.

Potentialen för en enskild medlem definieras som det maximalt möjliga värdet av deras nettovinst (lycka minus ansträngning) som de skulle kunna uppnå genom att välja sin ansträngningsnivå optimalt. Dessa träningspass är helt teoretiska; de används endast för tränarens dagliga rapport, och medlemmarnas faktiska skicklighetsnivåer förblir oförändrade från dag till dag.

Din uppgift är att hjälpa tränaren att beräkna klubbens totala potential i slutet av varje dag under rekryteringsperioden.

Indata

Den första raden i indata innehåller ett heltal $n$ ($1 \le n \le 10^5$), som representerar antalet dagar klubben rekryterar medlemmar.

Den andra raden innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), där $a_i$ är den initiala skicklighetsnivån för medlemmen som går med dag $i$.

Utdata

Skriv ut $n$ heltal på en enda rad. Det $k$-te heltalet ska vara klubbens totala potential i slutet av dag $k$.

Exempel

Indata 1

8
1 2 3 1 2 3 2 3

Utdata 1

0 0 0 0 1 3 5 9

Indata 2

1
1

Utdata 2

0

Förklaring

Förklaring av exempel 1: Dag $5$ finns det $5$ medlemmar med skicklighetsnivåerna $[1, 2, 3, 1, 2]$. För medlem $1$: Det finns $3$ medlemmar som gick med senare med strikt högre skicklighet: medlem $2$, medlem $3$ och medlem $5$. Den maximala potentialen för medlem $1$ är $1$, vilket uppnås med någon av följande strategier:

• Om medlem $1$ betalar $1$ enhet ansträngning blir hens skicklighet $2$. Hen kommer ikapp eller passerar medlem $2$ och medlem $5$. Lyckan är $2$ enheter, och vinsten är $2 - 1 = 1$ enhet.
• Om medlem $1$ betalar $2$ enheter ansträngning blir hens skicklighet $3$. Hen kommer ikapp eller passerar medlemmarna $2$, $3$ och $5$. Lyckan är $3$ enheter, och vinsten är $3 - 2 = 1$ enhet.

De övriga medlemmarna har maximal potential $0$. Därför är den totala potentialen för dag $5$ lika med $1$.

Dag $8$ finns det $8$ medlemmar med skicklighetsnivåerna $[1, 2, 3, 1, 2, 3, 2, 3]$. De optimala ansträngningarna är $[2, 1, 0, 2, 1, 0, 1, 0]$ och de motsvarande maximala potentialerna är $[4, 2, 0, 2, 1, 0, 0, 0]$.