问题描述

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

找到介于 $1$ 和 $N$ 之间（包括边界）的整数 $i$，使得：

• $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$ 不包含大于 $A_4$ 的不同整数（没有这样的整数）。
• 对于 $A_5 = 2$，$A$ 包含 $2$ 个大于 $A_5$ 的不同整数：$7$ 和 $8$。
• 对于 $A_6 = 8$，$A$ 不包含大于 $A_6$ 的不同整数（没有这样的整数）。

因此，存在两个 $i$ 值，$i = 1$ 和 $i = 5$，使得 $A$ 刚好包含 $K = 2$ 个大于 $A_i$ 的不同整数。因此，$K = 2$ 的答案为 $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