103723: [Atcoder]ABC372 D - Buildings

Problem Statement

There are $N$ buildings, Building $1$, Building $2$, $\ldots$, Building $N$, arranged in a line in this order. The height of Building $i$ $(1 \leq i \leq N)$ is $H_i$.

For each $i = 1, 2, \ldots, N$, find the number of integers $j$ $(i < j \leq N)$ satisfying the following condition:

• There is no building taller than Building $j$ between Buildings $i$ and $j$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq H_i \leq N$
• $ H_i\neq H_j\ (i\neq j)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

For each $i = 1, 2, \ldots, N$, let $c_i$ be the number of $j$ satisfying the condition. Print $c_1, c_2, \ldots, c_N$ in order, separated by spaces.

Sample Input 1

5
2 1 4 3 5

Sample Output 1

3 2 2 1 0

For $i=1$, the integers $j$ satisfying the condition are $2$, $3$, and $5$: there are three. (Between Buildings $1$ and $4$, there is a building taller than Building $4$, which is Building $3$, so $j=4$ does not satisfy the condition.) Therefore, the first number in the output is $3$.

Sample Input 2

4
1 2 3 4

Sample Output 2

3 2 1 0

Sample Input 3

10
1 9 6 5 2 7 10 4 8 3

Sample Output 3

2 3 3 3 2 1 2 1 1 0

问题陈述

有N栋建筑，分别是建筑1、建筑2、…、建筑N，按此顺序排列成一行。建筑i的高度为$H_i$（$1 \leq i \leq N$）。

对于每个$i = 1, 2, \ldots, N$，找出满足以下条件的整数$j$（$i < j \leq N$）的数量：

• 在建筑$i$和建筑$j$之间没有比建筑$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