Corte de pelo


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

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.


Comments

There are no comments at the moment.