题目描述

長さ $N$ の数列 $A\ =\ (A_1,\ A_2,\ \ldots,\ A_N)$ が与えられます。 $K\ =\ 0,\ 1,\ 2,\ \ldots,\ N-1$ のそれぞれについて、下記の問題を解いてください。

$1$ 以上 $N$ 以下の整数 $i$ であって、次の条件を満たすものの個数を求めよ。

• $A$ に含まれる整数のうち $A_i$ より大きいものはちょうど $K$ 種類である。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$N$ 行出力せよ。 $i\ =\ 1,\ 2,\ \ldots,\ N$ について、$i$ 行目には $K\ =\ i-1$ の場合の問題の答えを出力せよ。

题目大意

你有一个序列 $A = (A_1, A_2 , \ ..., A_n)$ 你需要求有多少个数满足 $A$ 中有 $k$ 个不同的数 $\geq$ $a_i$ $(i \in [1, n])$

6
2 7 1 8 2 8

2
1
2
1
0
0

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\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$
• 入力はすべて整数

Sample Explanation 1

例として、$K\ =\ 2$ の場合の問題の答えを以下で求めます。 - $A_1\ =\ 2$ に関して、$A$ に含まれる整数のうち $A_1$ より大きいものは、$7,\ 8$ の $2$ 種類です。 - $A_2\ =\ 7$ に関して、$A$ に含まれる整数のうち $A_2$ より大きいものは、$8$ の $1$ 種類です。 - $A_3\ =\ 1$ に関して、$A$ に含まれる整数のうち $A_3$ より大きいものは、$2,\ 7,\ 8$ の $3$ 種類です。 - $A_4\ =\ 8$ に関して、$A$ に含まれる整数のうち $A_4$ より大きいものは、$0$ 種類です（存在しません）。 - $A_5\ =\ 2$ に関して、$A$ に含まれる整数のうち $A_5$ より大きいものは、$7,\ 8$ の $2$ 種類です。 - $A_6\ =\ 8$ に関して、$A$ に含まれる整数のうち $A_6$ より大きいものは、$0$ 種類です（存在しません）。 よって、$A$ に含まれる整数のうち$A_i$ より大きいものがちょうど $K\ =\ 2$ 種類であるような $i$ は、$i\ =\ 1$ と $i\ =\ 5$ の $2$ つです。よって、$K\ =\ 2$ の場合の答えは $2$ です。