第 (K+1) 大的数

题目描述

给你长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$。 对于每个 $K = 0, 1, 2, \ldots, N-1$,解决以下问题。

求满足以下条件的 $1$ 到 $N$(含)之间的整数 $i$ 的个数:

$A$ 中恰好有 $K$ 个不同的整数大于 $A_i$。

输入格式

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

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出 $N$ 行。 对于 $i = 1, 2, \ldots, N$,第 $i$ 行应输出 $K = i-1$ 时的答案。

样例

6
2 7 1 8 2 8

2
1
2
1
0
0

例如,我们来求 $K=2$ 时的答案。

对于 $A_1 = 2$,$A$ 中有 $2$ 个不同的整数大于 $A_1$:$7$ 和 $8$。

对于 $A_2 = 7$,$A$ 中有 $1$ 个不同的整数大于 $A_2$:$8$。

对于 $A_3 = 1$,$A$ 中有 $3$ 个不同的整数大于 $A_3$:$2, 7$ 和 $8$。

对于 $A_4 = 8$,$A$ 中有 $0$ 个不同的整数大于 $A_4$(不存在这样的整数)。

对于 $A_5 = 2$,$A$ 中有 $2$ 个不同的整数大于 $A_5$:$7$ 和 $8$。

对于 $A_6 = 8$,$A$ 中有 $0$ 个不同的整数大于 $A_6$(不存在这样的整数)。

因此,满足「$A$ 中恰好有 $K = 2$ 个不同的整数大于 $A_i$」的 $i$ 有 $i = 1$ 和 $i = 5$ 两个。所以 $K = 2$ 时的答案是 $2$。

1
1

1

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

2
1
2
1
2
1
1
0
0
0

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• 输入中的所有值均为整数。