配点 : $300$ 点

問題文

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

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

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

制約

• $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$ の場合の問題の答えを出力せよ。

6
2 7 1 8 2 8

2
1
2
1
0
0

例として、$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$ です。

1
1

1

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

2
1
2
1
2
1
1
0
0
0