Un club di corsa sta reclutando membri e cresce rapidamente, con esattamente un nuovo membro che si unisce ogni giorno. Ogni membro arriva con uno specifico livello di abilità iniziale e gli viene assegnato un ID univoco basato sull'ordine di arrivo.

Alla fine di ogni giornata, all'allenatore piace calcolare una metrica che chiama il "potenziale totale" del club. Questo valore è semplicemente la somma dei potenziali individuali di tutti i membri attuali. Per mantenere motivati i membri, il potenziale di un membro viene calcolato attraverso uno scenario ipotetico che prevede un singolo allenamento intenso.

In questo allenamento immaginario, un membro può scegliere di impiegare una certa quantità di sforzo per aumentare temporaneamente il proprio livello di abilità. Per ogni $1$ unità di sforzo spesa, il suo livello di abilità aumenta di esattamente $1$ unità. In cambio, guadagna $1$ unità di "felicità" per ogni altro membro attualmente nel club che:

• si è unito al club strettamente dopo di lui; e
• era originariamente strettamente più abile di lui, ma ora è stato raggiunto o superato grazie all'allenamento.

Si noti che durante questo calcolo viene aumentato solo il livello di abilità di quel membro, mentre i livelli di abilità di tutti gli altri membri rimangono fissi ai loro valori originali.

Il potenziale di un singolo membro è definito come il massimo valore possibile del suo guadagno netto (felicità meno sforzo) che potrebbe ottenere scegliendo il proprio livello di sforzo in modo ottimale. Questi allenamenti sono interamente teorici; vengono utilizzati solo per il rapporto giornaliero dell'allenatore e i livelli di abilità effettivi dei membri rimangono invariati di giorno in giorno.

Il tuo compito è aiutare l'allenatore a calcolare il potenziale totale del club alla fine di ogni giorno del periodo di reclutamento.

Input

La prima riga dell'input contiene un intero $n$ ($1 \le n \le 10^5$), che rappresenta il numero di giorni in cui il club recluta membri.

La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), dove $a_i$ è il livello di abilità iniziale del membro che si unisce il giorno $i$.

Output

Stampa $n$ interi su una singola riga. Il $k$-esimo intero deve essere il potenziale totale del club alla fine del giorno $k$.

Esempi

Input 1

8
1 2 3 1 2 3 2 3

Output 1

0 0 0 0 1 3 5 9

Input 2

1
1

Output 2

0

Note

Spiegazione dell'Esempio 1: Il giorno $5$, ci sono $5$ membri con livelli di abilità $[1, 2, 3, 1, 2]$. Per il membro $1$: Ci sono $3$ membri entrati successivamente con abilità strettamente superiori: il membro $2$, il membro $3$ e il membro $5$. Il potenziale massimo per il membro $1$ è $1$, ottenuto tramite una delle seguenti strategie:

• Se il membro $1$ paga $1$ unità di sforzo, la sua abilità diventa $2$. Raggiungerà o supererà il membro $2$ e il membro $5$. La felicità è di $2$ unità e il guadagno è $2 - 1 = 1$ unità.
• Se il membro $1$ paga $2$ unità di sforzo, la sua abilità diventa $3$. Raggiungerà o supererà i membri $2$, $3$ e $5$. La felicità è di $3$ unità e il guadagno è $3 - 2 = 1$ unità.

Gli altri membri hanno potenziale massimo $0$. Pertanto, il potenziale totale per il giorno $5$ è $1$.

Il giorno $8$, ci sono $8$ membri con livelli di abilità $[1, 2, 3, 1, 2, 3, 2, 3]$. Gli sforzi ottimali sono $[2, 1, 0, 2, 1, 0, 1, 0]$ e i corrispondenti potenziali massimi sono $[4, 2, 0, 2, 1, 0, 0, 0]$.