AT_abc273_c [ABC273C] (K+1)-th Largest Number

[problemUrl]: https://atcoder.jp/contests/abc273/tasks/abc273_c 長さ $ 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 $ の場合の問題の答えを出力せよ。

### 制約 - $ 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 $ です。