← 返回题目列表

AtCoder · abc372_d

G. 建筑物

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

分数: 400 点

问题陈述

有 N 建筑物, 建筑物 1, 建筑 2, \ldots, 建筑 N,按此顺序排成一行。建筑物高度 i (1 \leq i \leq N) is H_i.

对于每个 i = 1, 2, \ldots, N,查找整数的个数 j (i < j \leq N) 满足以下条件:

  • 没有比建筑物更高的建筑物 j 建筑物之间 i 和 j.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq H_i \leq N
  • H_i\neq H_j\ (i\neq j)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
H_1 H_2 \ldots H_N

输出

对于每个 i = 1, 2, \ldots, N,让 c_i 是数量 j 满足条件。打印 c_1, c_2, \ldots, c_N 按顺序排列,用空格分隔。


示例输入 1

5
2 1 4 3 5

示例输出 1

3 2 2 1 0

对于 i=1,整数 j 满足条件的是 2, 3,和 5:有三个。 (建筑物之间 1 和 4,有一栋大楼比大楼还高 4,这是建筑 3,所以 j=4 不满足条件。)因此,输出中的第一个数字是 3.


示例输入 2

4
1 2 3 4

示例输出 2

3 2 1 0

示例输入 3

10
1 9 6 5 2 7 10 4 8 3

示例输出 3

2 3 3 3 2 1 2 1 1 0