Algo raro ha pasado en Isla Grande, los ciudadanos estaban haciendo tranquilamente una cola, cuando de pronto se empezaron a multiplicar, al parecer debido a la radiacion solar. Multiples clones de cada persona han aparecido regados por toda la cola. Como ahora pueden haber ciudadanos repetidos se quiere saber: para todo ~k~ de ~1~ a ~N~, donde ~N~ es la cantidad de personas en la cola, cuantos pares ~(i,j)~ tal que ~1 \leq i<j\leq k~ existen que cumplen que ~a_i \mathrel \neq a_j~.

Subtareas:

Todas las subtareas cumplen que ~ 1 \leq N \leq 10^{5} ~ y ~1 \leq a_i \leq N~

• Subtarea 1(10 puntos): ~ 1 \leq a_i \leq min(2,N)~.
• Subtarea 2 (20 puntos): ~ 1 \leq N \leq 400 ~.
• Subtarea 3 (30 puntos): ~ 1 \leq N \leq 3000 ~.
• Subtarea 4 (40 puntos): Sin restricciones adicionales.

Entrada

La primera linea de la entrada consiste en un entero ~N~ que indica el numero de personas en la cola. En la segunda linea se le daran ~N~ enteros ~1\leq a_i<N~

Salida

Usted debe imprimir ~N~ enteros, donde el k-esimo indica cuantos pares ~(i,j)~ existen tal que ~1 \leq i<j\leq k~ y ~a_i \mathrel \neq a_j~

Entrada de ejemplo 1:

6
1 2 1 3 3 1

Salida de ejemplo 1:

0 1 2 5 8 11

Entrada de ejemplo 2:

8
1 2 2 1 2 2 1 2

Salida de ejemplo 2:

0 1 2 4 6 8 12 15