高楼

题目描述

有 $N$ 栋建筑，按顺序排成一行，分别称为建筑 $1$、建筑 $2$、$\ldots$、建筑 $N$。建筑 $i$ $(1 \leq i \leq N)$ 的高度为 $H_i$。

对每个 $i = 1, 2, \ldots, N$，求满足以下条件的整数 $j$ $(i \lt j \leq N)$ 的个数：

在建筑 $i$ 和建筑 $j$ 之间，没有比建筑 $j$ 更高的建筑。

输入格式

输入按以下格式从标准输入给出：

$N$
$H_1$ $H_2$ $\ldots$ $H_N$

输出格式

对每个 $i = 1, 2, \ldots, N$，令 $c_i$ 为满足条件的 $j$ 的个数。按顺序输出 $c_1, c_2, \ldots, c_N$，用空格分隔。

样例

5
2 1 4 3 5

3 2 2 1 0

对于 $i=1$，满足条件的整数 $j$ 是 $2$、$3$ 和 $5$，共三个。（在建筑 $1$ 和建筑 $4$ 之间，有比建筑 $4$ 更高的建筑，即建筑 $3$，因此 $j=4$ 不满足条件。）因此，输出的第一个数是 $3$。

4
1 2 3 4

3 2 1 0

10
1 9 6 5 2 7 10 4 8 3

2 3 3 3 2 1 2 1 1 0

数据范围

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