1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
const int MX=500100;
int x,n,cnt[MX];
int main() {
  scanf("%d",&n);
  for (int i=0; i<n; i++) {
    scanf("%d",&x);
    ++cnt[x];
  }
  sort(cnt+1,cnt+n+1);
  int cur=0;
  for (int i=n; i>0; i--) {
    cur+=cnt[i]*2-1;
    if (cur>=n) { printf("%d\n",n-i+1); return 0; }
  }
  return 0;
}