#donuts20153. [donuts_2015_3]行列のできるドーナツ屋

[donuts_2015_3]行列のできるドーナツ屋

問題文

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

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

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

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


入力

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

NN H1H_1 H2H_2 ... HNH_N

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

部分点

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

  • N100N ≦ 100 を満たすテストケースすべてに正解した場合は 1010 点が与えられる。
  • N5000N ≦ 5000 を満たすテストケースすべてに正解した場合は 4040 点が与えられる。

出力

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


入力例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