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
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <vector>
#include <functional>
#include <bits/stdc++.h>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cctype>
#include <bitset>

using namespace std;

map <int,int> lider;
vector < pair<int,int> > ilosci;

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

int ile, wyraz, rozne, opusc, poza;

cin >> ile;
for (int n=1; n<=ile; n++)
{
  cin >> wyraz;
  ++lider[wyraz];
}
for (const auto& n : lider)
  ilosci.push_back(make_pair(n.second,n.second));
//for (int n=0; n<wejscie.size(); n++)
//  cout << wejscie[n] << " ";
//cout << endl;
sort(ilosci.begin(),ilosci.end());
//for (int n=0; n<ilosci.size(); n++)
//  cout << ilosci[n].first << " ";
//cout << endl;
//for (int n=0; n<ilosci.size(); n++)
//  cout << ilosci[n].second << " ";
//cout << endl;


//opusc=0;
//rozne=ilosci.size()-1;


if (ile==1)
  cout << ile;
else
  if (ilosci[rozne].first>ile/2)
	cout << 1;
  else
  {

opusc=0;
rozne=ilosci.size()-1;

    int ilelid=0;
	poza=0;
	while ((ilosci[rozne].first>1) && (rozne>0))
	{
	  ilelid=ilelid+1;
	  poza=ilosci[rozne].first-1;
	  rozne=rozne-1;
//	  cout << poza << " " << ilosci[rozne] << " " << opusc << " " << rozne << " " << ilelid << endl;
//      while ((poza-ilosci[rozne]>=0) && (rozne>0))
//      {
//	    poza=poza-ilosci[rozne];
//	    rozne=rozne-1;
//      }
	  while (poza-ilosci[opusc].first>=0)
	  {
		poza=poza-ilosci[opusc].first;
		++opusc;
//	    cout << poza << "--" << ilosci[opusc] << " " << rozne << " " << opusc << " " << ilelid << endl;
	  }
	  if (poza!=0)
		ilosci[opusc].first=poza;
	}
    while (opusc<=rozne)
	{
//	  ilelid=ilelid+ilosci[opusc];
      ilelid=ilelid+1;
	  ++opusc;
	}
opusc=0;
rozne=ilosci.size()-1;
    int ilelid2=0;
	poza=0;
	while ((ilosci[rozne].second>1) && (rozne>0))
	{
	  ilelid2=ilelid2+1;
	  poza=ilosci[rozne].second-1;
	  rozne=rozne-1;
//	  cout << poza << " " << ilosci[rozne] << " " << opusc << " " << rozne << " " << ilelid << endl;
      while ((poza-ilosci[rozne].second>=0) && (rozne>0))
      {
	    poza=poza-ilosci[rozne].second;
	    rozne=rozne-1;
      }
	  while (poza-ilosci[opusc].second>=0)
	  {
		poza=poza-ilosci[opusc].second;
		++opusc;
//	    cout << poza << "--" << ilosci[opusc] << " " << rozne << " " << opusc << " " << ilelid << endl;
	  }
	  if (poza!=0)
		ilosci[opusc].second=poza;
	}
    while (opusc<=rozne)
	{
//	  ilelid=ilelid+ilosci[opusc];
      ilelid2=ilelid2+1;
	  ++opusc;
	}
	cout << min(ilelid,ilelid2);
  }

return 0;

}