Juoksuseura värvää jäseniä ja kasvaa nopeasti: joka päivä seuraan liittyy täsmälleen yksi uusi jäsen. Jokaisella jäsenellä on tietty alkutaitotaso, ja heille annetaan yksilöllinen tunniste (ID) liittymisjärjestyksen perusteella.

Jokaisen päivän päätteeksi valmentaja haluaa laskea mittarin, jota hän kutsuu seuran ”kokonaispotentiaaliksi”. Tämä arvo on yksinkertaisesti kaikkien nykyisten jäsenten henkilökohtaisten potentiaalien summa. Pitääkseen jäsenet motivoituneina jäsenen potentiaali lasketaan hypoteettisen ”entä jos” -skenaarion avulla, johon sisältyy yksi intensiivinen harjoitus.

Tässä kuvitteellisessa harjoituksessa jäsen voi päättää panostaa tietyn määrän vaivaa nostaakseen taitotasoaan tilapäisesti. Jokaista käytettyä $1$ vaivayksikköä kohden hänen taitotasonsa nousee täsmälleen $1$ yksiköllä. Vastineeksi hän saa $1$ yksikön ”onnellisuutta” jokaisesta muusta tällä hetkellä seurassa olevasta jäsenestä, joka:

• liittyi seuraan aidosti hänen jälkeensä; ja
• oli alun perin aidosti taitavampi kuin hän, mutta jonka hän on nyt saavuttanut tai ohittanut harjoituksen ansiosta.

Huomaa, että tämän laskennan aikana vain kyseisen jäsenen taitotasoa nostetaan, kun taas kaikkien muiden jäsenten taitotasot pysyvät alkuperäisissä arvoissaan.

Yksittäisen jäsenen potentiaali määritellään hänen nettohyötynsä (onnellisuus miinus vaiva) suurimmaksi mahdolliseksi arvoksi, jonka hän voisi saavuttaa valitsemalla vaivatasonsa optimaalisesti. Nämä harjoitukset ovat täysin teoreettisia; niitä käytetään vain valmentajan päivittäiseen raporttiin, ja jäsenten todelliset taitotasot pysyvät muuttumattomina päivästä toiseen.

Tehtäväsi on auttaa valmentajaa laskemaan seuran kokonaispotentiaali värväysjakson jokaisen päivän päätteeksi.

Syöte

Syötteen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^5$), joka kuvaa niiden päivien lukumäärää, joina seura värvää jäseniä.

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), missä $a_i$ on päivänä $i$ liittyvän jäsenen alkutaitotaso.

Tuloste

Tulosta $n$ kokonaislukua yhdelle riville. $k$-nnen kokonaisluvun tulee olla seuran kokonaispotentiaali päivän $k$ päätteeksi.

Esimerkit

Syöte 1

8
1 2 3 1 2 3 2 3

Tuloste 1

0 0 0 0 1 3 5 9

Syöte 2

1
1

Tuloste 2

0

Huomautus

Esimerkin 1 selitys: Päivänä $5$ seurassa on $5$ jäsentä, joiden taitotasot ovat $[1, 2, 3, 1, 2]$. Jäsenelle $1$: On $3$ myöhemmin liittynyttä jäsentä, joilla on aidosti korkeampi taitotaso: jäsen $2$, jäsen $3$ ja jäsen $5$. Jäsenen $1$ maksimipotentiaali on $1$, joka saavutetaan jommallakummalla seuraavista strategioista:

• Jos jäsen $1$ panostaa $1$ yksikön vaivaa, hänen taidostaan tulee $2$. Hän saavuttaa tai ohittaa jäsenen $2$ ja jäsenen $5$. Onnellisuus on $2$ yksikköä ja nettohyöty on $2 - 1 = 1$ yksikkö.
• Jos jäsen $1$ panostaa $2$ yksikköä vaivaa, hänen taidostaan tulee $3$. Hän saavuttaa tai ohittaa jäsenet $2$, $3$ ja $5$. Onnellisuus on $3$ yksikköä ja nettohyöty on $3 - 2 = 1$ yksikkö.

Muilla jäsenillä maksimipotentiaali on $0$. Näin ollen päivän $5$ kokonaispotentiaali on $1$.

Päivänä $8$ seurassa on $8$ jäsentä, joiden taitotasot ovat $[1, 2, 3, 1, 2, 3, 2, 3]$. Optimaaliset vaivat ovat $[2, 1, 0, 2, 1, 0, 1, 0]$ ja vastaavat maksimipotentiaalit ovat $[4, 2, 0, 2, 1, 0, 0, 0]$.