問題文

ドーナツ町には、毎日行列ができる超人気のドーナツ屋があります。このドーナツ屋には今 $N$ 人の人がまっすぐ一列に並んでいます。行列に並んでいる人は、自分の番が来る前にドーナツが売り切れてしまうのではないかと不安に思っています。ドーナツ屋の店長は、それぞれの人がどれくらい不安に思っているのかを表す「不安度」を計算してみることにしました。

前から $i$ 番目 $(1 ≦ i ≦ N)$ に並んでいる人を人 $i$ と呼ぶことにします。人 $i$ の身長は $H_i$ です。人 $i$ の「不安度」は「人 $i$ が前を見たときに見える人の数」です。人 $i$ が前を見たときに人 $j$ が見えるための条件は以下の通りです。

• 人 $i$ よりも 人 $j$ の方が前に並んでいる。すなわち、$j < i$ である。
• 人 $i$ と人 $j$ の間に人 $j$ より身長の高い人がいない。すなわち、$j < k < i$ かつ $H_j < H_k$ を満たすような $k$ が存在しない。

例えば、行列に並んでいる人の身長が前から順に $2,5,3,4,1$ なら、一番後ろに並んでいる人 $5$ が前を見たときに見える人は人 $2$ と人 $4$ の $2$ 人なので、人 $5$ の「不安度」は $2$ となります。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $H_1$ $H_2$ ... $H_N$

• $1$ 行目には、行列に並んでいる人数を表す整数 $N (1 ≦ N ≦ 10^5)$ が与えられる。
• $2$ 行目には、行列に並んでいる人の身長を表す $N$ 個の整数が空白区切りで与えられる。このうち $i$ 番目の整数 $H_i (1 ≦ H_i ≦ 10^6)$ は、人 $i$ の身長を表す。ただし、$p \\neq q$ のとき $H_p \\neq H_q$ であることが保証される。

部分点

この問題には部分点が設定されている。

• $N ≦ 100$ を満たすテストケースすべてに正解した場合は $10$ 点が与えられる。
• $N ≦ 5000$ を満たすテストケースすべてに正解した場合は $40$ 点が与えられる。

出力

出力は $N$ 行からなる。このうち $i$ 行目には、人 $i$ の「不安度」を表す $1$ つの整数を出力せよ。出力の末尾にも改行を入れること。

入力例1

5
2 5 3 4 1

出力例1

0
1
1
2
2

入力例2

1
1000000

出力例2

0

入力例3

8
66 52 56 32 27 50 72 23

出力例3

0
1
2
2
3
4
3
1