Hlaupaklúbburinn er að safna meðlimum og stækkar hratt, þar sem nákvæmlega einn nýr meðlimur bætist við á hverjum degi. Hver meðlimur kemur með ákveðið upphaflegt hæfnisstig og fær úthlutað einkvæmu auðkenni (ID) miðað við komuröð.

Í lok hvers dags finnst þjálfaranum gaman að reikna út mælikvarða sem hann kallar „heildarmöguleika“ klúbbsins. Þetta gildi er einfaldlega summan af einstaklingsbundnum möguleikum allra núverandi meðlima. Til að halda meðlimunum áhugasömum eru möguleikar meðlims reiknaðir út í gegnum ímyndaðar „hvað ef“ aðstæður sem fela í sér eina stranga æfingu.

Á þessari ímynduðu æfingu getur meðlimur valið að leggja á sig ákveðið erfiði til að hækka hæfnisstig sitt tímabundið. Fyrir hverja $1$ einingu af erfiði sem hann leggur á sig hækkar hæfnisstig hans um nákvæmlega $1$ einingu. Í staðinn fær hann $1$ einingu af „hamingju“ fyrir hvern annan meðlim sem nú er í klúbbnum og:

• gekk í klúbbinn strangt til tekið á eftir honum; og
• hafði upphaflega strangt til tekið hærri hæfni en hann, en hefur nú verið náð eða tekinn fram úr honum þökk sé æfingunni.

Athugið að við þennan útreikning hækkar aðeins hæfnisstig þessa tiltekna meðlims, á meðan hæfnisstig allra annarra meðlima haldast föst í upphaflegum gildum sínum.

Möguleikar einstaks meðlims eru skilgreindir sem hæsta mögulega gildi hreins ávinnings hans (hamingja mínus erfiði) sem hann gæti náð með því að velja erfiðisstig sitt á sem bestan hátt. Þessar æfingar eru alfarið fræðilegar; þær eru aðeins notaðar fyrir daglega skýrslu þjálfarans og raunveruleg hæfnisstig meðlima haldast óbreytt frá degi til dags.

Verkefni þitt er að hjálpa þjálfaranum að reikna út heildarmöguleika klúbbsins í lok hvers dags á nýliðunartímabilinu.

Inntak

Fyrsta línan í inntakinu inniheldur heiltölu $n$ ($1 \le n \le 10^5$), sem táknar fjölda daga sem klúbburinn safnar meðlimum.

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), þar sem $a_i$ er upphaflegt hæfnisstig meðlimsins sem bætist við á degi $i$.

Úttak

Prentið $n$ heiltölur í einni línu. $k$-ta heiltalan ætti að vera heildarmöguleikar klúbbsins í lok dags $k$.

Dæmi

Inntak 1

8
1 2 3 1 2 3 2 3

Úttak 1

0 0 0 0 1 3 5 9

Inntak 2

1
1

Úttak 2

0

Skýringar

Skýring á dæmi 1: Á degi $5$ eru $5$ meðlimir með hæfnisstigin $[1, 2, 3, 1, 2]$. Fyrir meðlim $1$: Það eru $3$ meðlimir sem bættust við síðar með strangt til tekið hærri hæfni: meðlimur $2$, meðlimur $3$ og meðlimur $5$. Hámarksmöguleikar meðlims $1$ eru $1$, sem næst með annarri hvorri af eftirfarandi aðferðum:

• Ef meðlimur $1$ leggur á sig $1$ einingu af erfiði verður hæfni hans $2$. Hann nær eða fer fram úr meðlim $2$ og meðlim $5$. Hamingjan er $2$ einingar og ávinningurinn er $2 - 1 = 1$ eining.
• Ef meðlimur $1$ leggur á sig $2$ einingar af erfiði verður hæfni hans $3$. Hann nær eða fer fram úr meðlimum $2$, $3$ og $5$. Hamingjan er $3$ einingar og ávinningurinn er $3 - 2 = 1$ eining.

Hinir meðlimirnir hafa hámarksmöguleika $0$. Því eru heildarmöguleikarnir fyrir dag $5$ jafnir $1$.

Á degi $8$ eru $8$ meðlimir með hæfnisstigin $[1, 2, 3, 1, 2, 3, 2, 3]$. Besta erfiðið er $[2, 1, 0, 2, 1, 0, 1, 0]$ og samsvarandi hámarksmöguleikar eru $[4, 2, 0, 2, 1, 0, 0, 0]$.