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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
map<int, int> zlicz;
priority_queue<pair<int, int>> maks;//#wystapien; czego
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> mini;
map<int, int> akt;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin>>n;
	int t[n];
	for(int i=0; i<n; i++){
		cin>>t[i];
		zlicz[t[i]]++;
	}
	for(auto i:zlicz){
		maks.push(mp(i.nd, i.st));
		mini.push(mp(i.nd, i.st));
	}
	int wynik=0;
	while(maks.size()){
		auto a=maks.top();
		if(zlicz[a.nd]!=a.st){
			if(zlicz[a.nd]){
				wynik++;//jeszcze cos zostalo tej liczby
			}
			break;
		}
		auto temp=a;
		a.st--;
		maks.pop();

		while(a.st && mini.top()!=temp){
			auto b=mini.top();
			mini.pop();
			if(b.st<=a.st){
				a.st-=b.st;
				zlicz[b.nd]=0;
			}
			else{
				b.st-=a.st;
				a.st=0;
				zlicz[b.nd]=b.st;
				mini.push(b);
			}
		}

		zlicz[a.nd]=0;//nie zaszkodzi
		wynik++;
	}
	cout<<wynik;
}