← 返回题目列表

AtCoder · code_festival_qualB_d

D. 登山者

中文机器翻译题面 查看原题

問題文

高桥是一名登山家,他攀登了今天存在的山脉。

在这山脉里 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