← 返回题目列表

AtCoder · abc273_c

F. 第 (K+1) 个最大数

中文机器翻译题面 查看原题

分数: 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