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
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <string>
#include <math.h>
#include <iomanip>
#include <complex>
#include <fstream>

#define ll long long
#define ull unsigned ll

#define pii pair<int,int>
#define pllll pair<long long, long long>
#define pullull pair<ull,ull>
#define pss pair<string, string>
#define pcc pair<char,char>
#define pdd pair<double,double>
#define pbb pair<bool bool>

#define pill pair<int,ll>
#define piull pair<int,ull>
#define pis pair<int,string>
#define pic pair<int,char>
#define pid pair<int,double>
#define pib pair<int,bool>

#define plli pair<ll,int>
#define pllull pair<ll,ull>
#define plls pair<ll,string>
#define pllc pair<ll,char>
#define plld pair<ll,double>
#define pllb pair<ll,bool>

#define pulli pair<ull,int>
#define pullll pair<ull,ll>
#define pulls pair<ull,string>
#define pullc pair<ull,char>
#define pulld pair<ull,double>
#define pullb pair<ull,bool>

#define psi pair<string,int>
#define psll pair<string,ll>
#define psull pair<string,ull>
#define	psc pair<string,char>
#define psd pair<string,double>
#define psb pair<string,bool>

#define pci pair<char,int>
#define pcll pair<char,ll>
#define pcull pair<char,ull>
#define pcs pair<char,string>
#define pcd pair<char,double>
#define pcb pair<char,string>

#define pdi pair<double,int>
#define pdll pair<double,ll>
#define pdull pair<double,ull>
#define pds pair<double,string>
#define pdc pair<double,char>
#define pdb pair<double,bool>

#define pbi pair<bool,int>
#define pbll pair<bool,ll>
#define pbull pair<bool,ull>
#define pbs pair<bool,string>
#define pbc pair<bool,char>
#define pbd pair<bool,double>

#define vc vector
#define cd complex<double>

const ll m1 = 1e9 + 7;

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
	//cin >> t;
	while (t--) {
		int n;
		cin >> n;

		vc<int> wyst(n + 10);
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			wyst[x]++;
		}

		vc<int> v;
		for (int i = 1; i <= n; i++) {
			if (wyst[i]) v.push_back(wyst[i]);
		}

		sort(v.begin(), v.end());
		int ileWywalic = n/2+1-v.back();
		int ans = 1;
		int ktoryNastepny = v.size() - 2;
		int ktoryKoniec = 0;
		while (ileWywalic>0 && ktoryKoniec<ktoryNastepny) {
			int ileMozna = v[ktoryNastepny];
			ileWywalic -= ileMozna;
			
			int ileJeszcze = ileMozna-1;
			while (ktoryKoniec < ktoryNastepny && ileJeszcze >= v[ktoryKoniec]) {
				ileJeszcze -= v[ktoryKoniec];
				ileWywalic -= v[ktoryKoniec];
				ktoryKoniec++;
			}

			if (ileJeszcze && ktoryKoniec<ktoryNastepny) {
				v[ktoryKoniec] -= ileJeszcze;
				ileMozna -= ileJeszcze;
			}

			ktoryNastepny--;
			ans++;
		}

		cout << ans << "\n";
	}
}