A Frane se le ha encomendado la tarea de clasificar una serie de números. La matriz consiste en N enteros, cada uno entre ~1~ y ~N~ (inclusive), con cada uno de los que aparecen exactamente una vez en la matriz. Frane ha ideado el siguiendo el algoritmo de clasificación que opera en ~N~ fases, y lo nombró turbosort

· En la primera fase, el número 1 se mueve a la posición 1 repetidamente

Intercambiando elementos consecutivos.

· En la segunda fase, el número ~N~ se mueve a la posición ~N~ de la misma manera.

· En la tercera fase, el número 2 se mueve a la posición 2.

· En la cuarta fase, el número ~N-1~ se mueve a la posición ~N-1~.

· Y así.

En otras palabras, cuando el número de la fase es impar, Frane elegirá el El número más pequeño aún no se ha elegido, y lo mueve a su posición final. En incluso Fases que elige el número más grande aún no elegido. Escribe un programa que, dada la matriz inicial, generar el número de swaps en cada fase del algoritmo.

Entrada

La primera línea contiene un entero ~N (1 <= N <= 100 000)~, el número de Elementos de la matriz. Cada una de las siguientes ~N~ líneas contiene un número entero entre ~1~ y ~N~ (inclusive), la matriz a clasificar. La matriz contendrá No hay duplicados.

Salida

Para cada una de las ~N~ fases, genere el número de swaps en una sola línea.

Tanteo

En casos de prueba con un valor del 70% de los puntos, N será inferior a 100.

Ejemplo #1 de Entrada

3
2
1
3

Ejemplo #1 de Salida

1
0
0

Ejemplo #2 de Entrada

5
5
4
3
2
1

Ejemplo #2 de Salida

4
3
2
1
0

Ejemplo #3 de Entrada

7
5
4
3
7
1 
2
6

Ejemplo #3 de Salida

4
2
3
0
2
1
0