AT_abc372_d [ABC372D] Buildings

题目描述

这里有 $N$ 栋房子，从 $1$ 到 $N$ 依次编号。它们按照顺序排成一排。第 $i(1\le i\le N)$ 的房子的高度为 $H_i$。

对于每一个 $i=1,2,\dots,N$，找到满足以下条件的整数 $j(i<j\le N)$ 的数量：

• 没有一栋在 $i$ 和 $j$ 之间的房子比 $j$ 要高。

输入格式

第一行，一个整数 $N$。

第二行，有 $N$ 个整数，表示每栋房子的高度。

输出格式

对于每一个 $i=1,2,\dots,n$，令 $c_i$ 为满足条件的 $j$ 的数量。输出 $N$ 个整数 $c_1,c_2,\dots,c_N$。

样例 1 解释

当 $i=1$ 时，满足条件的 $j$ 有 $2,3$ 和 $5$，一共 $3$ 个。（在第 $1$ 栋房子和第 $4$ 栋房子之间，房子 $3$ 比房子 $4$ 高，所以 $j=4$ 不满足条件。）所以第一个数输出 $3$。

输入输出样例 #1

输入 #1

5
2 1 4 3 5

输出 #1

3 2 2 1 0

输入输出样例 #2

输入 #2

4
1 2 3 4

输出 #2

3 2 1 0

输入输出样例 #3

输入 #3

10
1 9 6 5 2 7 10 4 8 3

输出 #3

2 3 3 3 2 1 2 1 1 0

说明/提示

• $1\le N\le 2\times 10^5$
• $1\le H_i\le N$
• $H_i\not=H_j(i\not= j)$
• 所有输入都为整数