Los corredores de una carrera de larga distancia han pasado el punto de retorno. Cada corredor tiene una habilidad entera distinta; un valor mayor indica un corredor más fuerte. Un corredor puede adelantar a cualquier corredor que esté delante y tenga una habilidad menor, pero no puede adelantar a uno más fuerte.

Dadas las habilidades en el orden actual de la carrera, de delante hacia atrás, encuentra la mejor posición que puede alcanzar cada corredor.

Por ejemplo, las habilidades $2,8,10,7,1,9,4,15$ dan las mejores posiciones $1,1,1,3,5,2,5,1$. El cuarto corredor, con habilidad $7$, puede adelantar al corredor de habilidad $2$, pero no a los de habilidades $8$ y $10$, por lo que su mejor posición es $3$.

Entrada

La primera línea contiene $N$ ($3 \le N \le 500000$). Cada una de las siguientes $N$ líneas contiene la habilidad de un corredor, en el orden actual de la carrera. Las habilidades son enteros distintos entre $1$ y $10^9$, ambos inclusive.

Salida

Imprime $N$ líneas en el orden de entrada, indicando la mejor posición de cada corredor. La posición 1 es el primer puesto.

Ejemplos

Entrada 1

8
2
8
10
7
1
9
4
15

Salida 1

1
1
1
3
5
2
5
1