問題文
高桥是一名登山家,他攀登了今天存在的山脉。
在这山脉里 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