Un club de atletismo está reclutando miembros y creciendo rápidamente, con exactamente un nuevo miembro uniéndose cada día. Cada miembro llega con un nivel de habilidad inicial específico y se le asigna un ID único basado en su orden de llegada.

Al final de cada día, al entrenador le gusta calcular una métrica que llama el "potencial total" del club. Este valor es simplemente la suma de los potenciales individuales de todos los miembros actuales. Para mantener motivados a los miembros, el potencial de un miembro se calcula mediante un escenario hipotético que involucra un único entrenamiento intenso.

En este entrenamiento imaginario, un miembro puede elegir realizar cierta cantidad de esfuerzo para aumentar temporalmente su nivel de habilidad. Por cada $1$ unidad de esfuerzo que gasta, su nivel de habilidad aumenta en exactamente $1$ unidad. A cambio, gana $1$ unidad de "felicidad" por cada otro miembro actualmente en el club que:

• se unió al club estrictamente después que él; y
• originalmente tenía una habilidad estrictamente mayor que la suya, pero ahora ha sido alcanzado o superado gracias al entrenamiento.

Ten en cuenta que durante este cálculo, solo aumenta el nivel de habilidad de ese miembro, mientras que los niveles de habilidad de todos los demás miembros permanecen fijos en sus valores originales.

El potencial de un solo miembro se define como el valor máximo posible de su ganancia neta (felicidad menos esfuerzo) que podría lograr eligiendo su nivel de esfuerzo de manera óptima. Estos entrenamientos son completamente teóricos; se utilizan solo para el informe diario del entrenador, y los niveles de habilidad reales de los miembros permanecen sin cambios de un día para otro.

Tu tarea es ayudar al entrenador a calcular el potencial total del club al final de cada día del período de reclutamiento.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 10^5$), que representa el número de días que el club está reclutando miembros.

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), donde $a_i$ es el nivel de habilidad inicial del miembro que se une el día $i$.

Salida

Imprime $n$ enteros en una sola línea. El $k$-ésimo entero debe ser el potencial total del club al final del día $k$.

Ejemplos

Entrada 1

8
1 2 3 1 2 3 2 3

Salida 1

0 0 0 0 1 3 5 9

Entrada 2

1
1

Salida 2

0

Notas

Explicación del Ejemplo 1: En el día $5$, hay $5$ miembros con niveles de habilidad $[1, 2, 3, 1, 2]$. Para el miembro $1$: Hay $3$ miembros que se unieron más tarde con habilidades estrictamente mayores: el miembro $2$, el miembro $3$ y el miembro $5$. El potencial máximo para el miembro $1$ es $1$, logrado mediante cualquiera de las siguientes estrategias:

• Si el miembro $1$ paga $1$ unidad de esfuerzo, su habilidad se convierte en $2$. Alcanzará o superará al miembro $2$ y al miembro $5$. La felicidad es de $2$ unidades y la ganancia es $2 - 1 = 1$ unidad.
• Si el miembro $1$ paga $2$ unidades de esfuerzo, su habilidad se convierte en $3$. Alcanzará o superará a los miembros $2$, $3$ y $5$. La felicidad es de $3$ unidades y la ganancia es $3 - 2 = 1$ unidad.

Los demás miembros tienen un potencial máximo de $0$. Por lo tanto, el potencial total para el día $5$ es $1$.

En el día $8$, hay $8$ miembros con niveles de habilidad $[1, 2, 3, 1, 2, 3, 2, 3]$. Los esfuerzos óptimos son $[2, 1, 0, 2, 1, 0, 1, 0]$ y los potenciales máximos correspondientes son $[4, 2, 0, 2, 1, 0, 0, 0]$.