1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//Maksymilian Zakrzewski XIII LO w Szczecinie
#include <bits/stdc++.h>

using namespace std;

auto main()->int{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
        int n;
	cin >> n;
	int tab[n];
	long long sum = 0, sum2 = 0;
	for(int i = 0; i < n; i++){
		cin >> tab[i];
	}
	int ile[n+1] = {0};
	for(auto x : tab) ile[x]++;
	vector<int> xd;
	for(auto x : ile){
		sum += x;       
		if(x>0) xd.push_back(x);
	}
	sort(xd.rbegin(), xd.rend());
	for(int i = 0; i < xd.size(); i++){
		sum2 += xd[i];
		int s = sum - sum2;
//debug		cout << sum2 << ' ' << sum-sum2 + i + 1 << endl;
		if(sum2 >= sum-sum2 + i + 1){
			cout << i + 1 << endl;
			return 0;
		}
	}
	cout << xd.size() << endl;
	return 0;
}