题目描述

给定长度为N的数列A = (A₁, A₂, …, A_N)， 和 整数K = 0, 1, 2, …, N−1，请问 A 中有多少个A_i （1 <= i <= n) 恰好包含 k 个大于它的不同正整数。

【输入格式】

共两行，
第一行，一个正整数 N，表示输入数的个数；
第二行，N个整数 A_i 。

【输出格式】

共N行，每行一个整数，分别表示K = 0, 1, 2, …, N−1时的答案。

【输入输出样例#1】

输入#1

6
2 7 1 8 2 8

输出#1

2
1
2
1
0
0

【输入输出样例#2】

输入#2

1
1

输出#2

1

【输入输出样例#3】

输入#3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

输出#3

2
1
2
1
2
1
1
0
0
0

【说明提示】

对于样例1的说明：
当 K 为 2 时.
A₁ = 2，A包含了 2 个不同的大于它的正整数：7、8；
A₂ = 7，A包含了 1 个不同的大于它的正整数：8；
A₃ = 1，A包含了 3 个不同的大于它的正整数：2、7、8；
A₄ = 8，A包含了 0 个不同的大于它的正整数：无；
A₅ = 2，A包含了 2 个不同的大于它的正整数：7、8；
A₆ = 8，A包含了 0 个不同的大于它的正整数：无；
​

【数据范围】

1 ≤ N ≤ 2 × 10⁵

1 ≤ A_i ≤ 10⁹

【代码样例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2 * 1e5 + 5;
int n;
int a[MAXN];
int b[MAXN];
int k[MAXN];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1); //排序
	//去重
	int j = 1;
	b[j] = a[1];
	for (int i = 2; i <= n; i++) {
		if (a[i] != b[j]) {
			j++;
			b[j] = a[i];
		}
	}
	for (int i = 1; i <= n; i++) {
		int x = upper_bound(b + 1, b + j + 1, a[i]) - b;
		k[j - x + 1]++;
	}
	for (int i = 0; i < n; i++) {
		cout << k[i] << endl;
	}


}