C - (K+1)-th Largest Number Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

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

入力例 1

6
2 7 1 8 2 8

出力例 1

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 です。

入力例 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

Score : 300 points

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. For each K = 0, 1, 2, \ldots, N-1, solve the following problem.

Find the number of integers i between 1 and N (inclusive) such that:

  • A contains exactly K distinct integers greater than A_i.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print N lines. For i = 1, 2, \ldots, N, the i-th line should contain the answer for K = i-1.

Sample Input 1

6
2 7 1 8 2 8

Sample Output 1

2
1
2
1
0
0

For example, we will find the answer for K=2.

  • Regarding A_1 = 2, A contains 2 distinct integers greater than A_1: 7 and 8.
  • Regarding A_2 = 7, A contains 1 distinct integer greater than A_2: 8.
  • Regarding A_3 = 1, A contains 3 distinct integers greater than A_3: 2, 7, and 8.
  • Regarding A_4 = 8, A contains 0 distinct integers greater than A_4 (there is no such integer).
  • Regarding A_5 = 2, A contains 2 distinct integers greater than A_5: 7 and 8.
  • Regarding A_6 = 8, A contains 0 distinct integers greater than A_6 (there is no such integer).

Thus, there are two i's, i = 1 and i = 5, such that A contains exactly K = 2 distinct integers greater than A_i. Therefore, the answer for K = 2 is 2.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

Sample Output 3

2
1
2
1
2
1
1
0
0
0