Os corredores de uma corrida de longa distância já passaram pelo ponto de retorno. Cada corredor tem uma habilidade inteira distinta; um valor maior indica um corredor mais forte. Um corredor pode ultrapassar qualquer corredor à sua frente cuja habilidade seja menor, mas não pode ultrapassar um corredor mais forte.

Dadas as habilidades na ordem atual da corrida, da frente para trás, determine a melhor posição que cada corredor pode alcançar.

Por exemplo, as habilidades $2,8,10,7,1,9,4,15$ dão as melhores posições $1,1,1,3,5,2,5,1$. O quarto corredor, com habilidade $7$, pode ultrapassar o corredor com habilidade $2$, mas não os de habilidades $8$ e $10$, pelo que a sua melhor posição é $3$.

Entrada

A primeira linha contém $N$ ($3 \le N \le 500000$). Cada uma das $N$ linhas seguintes contém a habilidade de um corredor, na ordem atual da corrida. As habilidades são inteiros distintos entre $1$ e $10^9$, inclusive.

Saída

Imprima $N$ linhas na ordem de entrada, indicando a melhor posição de cada corredor. A posição 1 corresponde ao primeiro lugar.

Exemplos

Entrada 1

8
2
8
10
7
1
9
4
15

Saída 1

1
1
1
3
5
2
5
1