分数: 300 点
问题陈述
给你一个序列 A = (A_1, A_2, \ldots, A_N) 长度 N。 对于每个 K = 0, 1, 2, \ldots, N-1,解决以下问题。
查找整数的个数 i 之间 1 和 N (含)使得:
- A 恰好包含 K 不同的整数大于 A_i.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印 N 行。 对于 i = 1, 2, \ldots, N, i- 第行应包含以下问题的答案 K = i-1.
示例输入 1
6 2 7 1 8 2 8
示例输出 1
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 (没有这样的整数)。
因此,有两个 i的, i = 1 和 i = 5,这样 A 恰好包含 K = 2 不同的整数大于 A_i。 因此,答案为 K = 2 is 2.
示例输入 2
1 1
示例输出 2
1
示例输入 3
10 979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527
示例输出 3
2 1 2 1 2 1 1 0 0 0