D - 登山家 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は登山家で、いまある山脈を登っています。

この山脈には N 個の山小屋が東西へ一直線上に並んでおり、各山小屋には西から東へ順番に、 1 から N までの番号がつけられています。

i 番目の山小屋は標高 h_i のところに建てられています。

高橋君は各山小屋から、いくつの山小屋を見ることが出来るのか気になりました。

i 番目の山小屋から j 番目の山小屋が見える条件は、その間にある山小屋と j 番目の山小屋の標高が全て h_i 以下であることです。

各山小屋から見ることが出来る山小屋の個数を求めてください。

なお、 i 番目の山小屋から見ることができる山小屋に i 番目の山小屋自身は含まれません。

入力

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

N
h_1
h_2
:
h_N
  • 1 行目には山小屋の数 N (1 ≦ N ≦ 10^5) が与えられる。
  • 2 行目からの N 行のうち i 行目には i 番目の山小屋の標高を表す整数 h_i (1 ≦ h_i ≦ 10^5) が与えられる。

部分点

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

  • 1 ≦ N ≦ 3,000を満たすデータセットに正解した場合は 30 点が与えられる。
  • 1 ≦ N ≦ 10^5を満たすデータセットに正解した場合はさらに 70 点が与えられる。合計で100点となる。

出力

出力は N 行からなる。 i 行目には i 番目の山小屋から見える山小屋の個数を出力せよ。

入力例1

3
1
2
3

出力例1

0
1
2

どの山小屋もそれ自身より西側にある全ての山小屋のみを見ることができます。

入力例2

5
1
2
3
2
1

出力例2

0
1
4
1
0

1, 5 番目の山小屋はどの山小屋も見ることができません。 2 番目の山小屋は 1 番目の山小屋を見ることができます。 4 番目の山小屋は 5 番目の山小屋を見ることができます。 3 番目の山小屋はそれ以外すべての山小屋を見ることができます。

入力例3

5
3
2
1
2
3

出力例3

4
2
0
2
4

それ自身と同じ標高の山小屋もギリギリ見えることに注意してください。

入力例4

8
4
3
2
3
4
3
2
1

出力例4

7
2
0
2
7
2
1
0