Descripción

Cansado de su rebelde mechón de cabello, OCI-Cub decide cortarse el cabello. Él tiene ~N~ mechones de cabello dispuestos en una línea, y el mechón ~i~ tiene una longitud inicial de ~A_i~ micrómetros. Idealmente, él quiere que su cabello sea monótonamente creciente en longitud, por lo que define la "maldad" de su cabello como el número de inversiones: parejas ~(i,j)~ tales que ~i < j~ y ~A_i > A_j~.

Para cada valor de ~j=0,1,...,N-1~, OCI-Cub quisiera saber la maldad de su cabello si todos los mechones con longitud mayor a ~j~ se reducen a una longitud exactamente igual a ~j~.

(Dato curioso: la cabeza humana promedio tiene alrededor de ~10^5~ cabellos).

Entrada

La primera línea contiene ~N~.

La segunda línea contiene ~N~ enteros ~A_1, A_2, ..., A_N~ separados por espacios.

Salida

Para cada valor de ~j=0,1,...,N-1~, imprime en una línea nueva la maldad del cabello de OCI-Cub. Ten en cuenta que el tamaño de los enteros involucrados en este problema puede requerir el uso de tipos de datos enteros de 64 bits (por ejemplo, "long long" en C/C++).

Restricciones

~2 \le N \le 10^5~

~0 \le A_i \le N~

Subtareas

Casos 2: ~N \le 100~

Casos 3-5: ~N \le 5000~

Casos 6-13: Sin restricciones adicionales

Entrada ejemplo

5
5 2 3 3 0

Salida ejemplo

0
4
4
5
7

La cuarta línea de salida describe el número de inversiones cuando los mechones de GJ se reducen a una longitud de 3. Luego, ~A=[3,2,3,3,0]~ tiene cinco inversiones: ~A_1~ > ~A_2~, ~A_1~ > ~A_5~, ~A_2~ > ~A_5~, ~A_3~ > ~A_5~ y ~A_4~ > ~A_5~.