C - 行列のできるドーナツ屋 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

ドーナツ町には、毎日行列ができる超人気のドーナツ屋があります。このドーナツ屋には今 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